Pengira Algoritma Luhn

Kalkulator Algoritma Luhn

Pengenalan

Algoritma Luhn, juga dikenali sebagai "modulus 10" atau "mod 10" algoritma, adalah formula checksum yang mudah digunakan untuk mengesahkan pelbagai nombor pengenalan, seperti nombor kad kredit, Nombor Insurans Sosial Kanada, nombor IMEI, dan nombor Pengenal Penyedia Nasional di Amerika Syarikat. Kalkulator ini membolehkan anda mengesahkan nombor menggunakan algoritma Luhn dan menghasilkan nombor yang sah yang lulus pemeriksaan Luhn.

Cara Algoritma Luhn Berfungsi

Algoritma Luhn berfungsi seperti berikut:

1. Bermula dari digit paling kanan (tidak termasuk digit semakan) dan bergerak ke kiri, gandakan nilai setiap digit kedua.
2. Jika hasil operasi penggandaan ini lebih daripada 9, tolak 9 dari hasil tersebut.
3. Jumlahkan semua digit dalam urutan yang dihasilkan.
4. Jika jumlah modulo 10 sama dengan 0 (jika jumlah berakhir dengan sifar), maka nombor itu adalah sah mengikut formula Luhn; jika tidak, ia tidak sah.

Berikut adalah representasi visual algoritma Luhn:

Formula

Algoritma Luhn boleh dinyatakan secara matematik seperti berikut:

Biarkan $d_i$ menjadi digit ke-$i$, mengira dari digit paling kanan (tidak termasuk digit semakan) dan bergerak ke kiri. Maka digit semakan $d_0$ dipilih supaya:

$(2d_{2n} \bmod 9 + d_{2n-1} + 2d_{2n-2} \bmod 9 + d_{2n-3} + \cdots + 2d_2 \bmod 9 + d_1 + d_0) \bmod 10 = 0$

Di mana $\bmod$ adalah operasi modulo.

Kes Penggunaan

Algoritma Luhn mempunyai pelbagai aplikasi dalam pelbagai bidang:

1. Pengesahan Kad Kredit: Kebanyakan nombor kad kredit disahkan menggunakan algoritma Luhn.
2. Nombor Insurans Sosial Kanada: Algoritma Luhn digunakan untuk mengesahkan kesahihan nombor pengenalan ini.
3. Nombor IMEI: Nombor IMEI telefon mudah alih mengandungi digit semakan yang disahkan oleh algoritma Luhn.
4. Nombor Pengenal Penyedia Nasional (NPI): Digunakan dalam sistem penjagaan kesihatan Amerika Syarikat, nombor ini disahkan menggunakan algoritma Luhn.
5. ISBN: Beberapa nombor ISBN-10 menggunakan varian algoritma Luhn untuk pengesahan.

Alternatif

Walaupun algoritma Luhn digunakan secara meluas, terdapat algoritma checksum lain untuk tujuan yang berbeza:

1. Algoritma Damm: Algoritma digit semakan lain yang mengesan semua ralat satu digit dan semua ralat transposisi bersebelahan.
2. Algoritma Verhoeff: Algoritma checksum yang lebih kompleks yang menangkap semua ralat satu digit dan kebanyakan ralat transposisi.
3. Digit semakan ISBN-13: Menggunakan algoritma yang berbeza daripada ISBN-10, yang berdasarkan algoritma Luhn.

Sejarah

Algoritma Luhn dicipta oleh Hans Peter Luhn, seorang saintis komputer IBM, pada tahun 1954. Luhn adalah pelopor dalam bidang sains maklumat dan diakui dengan beberapa inovasi, termasuk sistem pengindeksan KWIC (Kata Kunci Dalam Konteks).

Algoritma ini pada asalnya direka untuk melindungi daripada ralat tidak sengaja, bukan serangan berniat jahat. Penting untuk diperhatikan bahawa walaupun algoritma Luhn dapat mengesan banyak ralat biasa, ia bukan bentuk penyulitan yang selamat dan tidak boleh bergantung kepada untuk tujuan keselamatan data.

Walaupun usianya, algoritma Luhn tetap digunakan secara meluas kerana kesederhanaan dan keberkesanannya dalam menangkap ralat transkripsi yang biasa.

Contoh Pelaksanaan

Berikut adalah beberapa contoh kod untuk melaksanakan algoritma Luhn dalam pelbagai bahasa pengaturcaraan:

import random

def luhn_validate(number):
    digits = [int(d) for d in str(number)]
    checksum = 0
    for i in range(len(digits) - 1, -1, -1):
        d = digits[i]
        if (len(digits) - i) % 2 == 0:
            d = d * 2
            if d > 9:
                d -= 9
        checksum += d
    return checksum % 10 == 0

def generate_valid_number(length):
    digits = [random.randint(0, 9) for _ in range(length - 1)]
    checksum = sum(digits[::2]) + sum(sum(divmod(d * 2, 10)) for d in digits[-2::-2])
    check_digit = (10 - (checksum % 10)) % 10
    return int(''.join(map(str, digits + [check_digit])))

## Contoh penggunaan:
print(luhn_validate(4532015112830366))  # True
print(luhn_validate(4532015112830367))  # False
print(generate_valid_number(16))  # Menghasilkan nombor 16-digit yang sah

function luhnValidate(number) {
    const digits = number.toString().split('').map(Number);
    let checksum = 0;
    for (let i = digits.length - 1; i >= 0; i--) {
        let d = digits[i];
        if ((digits.length - i) % 2 === 0) {
            d *= 2;
            if (d > 9) d -= 9;
        }
        checksum += d;
    }
    return checksum % 10 === 0;
}

function generateValidNumber(length) {
    const digits = Array.from({length: length - 1}, () => Math.floor(Math.random() * 10));
    const checksum = digits.reduce((sum, digit, index) => {
        if ((length - 1 - index) % 2 === 0) {
            digit *= 2;
            if (digit > 9) digit -= 9;
        }
        return sum + digit;
    }, 0);
    const checkDigit = (10 - (checksum % 10)) % 10;
    return parseInt(digits.join('') + checkDigit);
}

// Contoh penggunaan:
console.log(luhnValidate(4532015112830366));  // true
console.log(luhnValidate(4532015112830367));  // false
console.log(generateValidNumber(16));  // Menghasilkan nombor 16-digit yang sah

import java.util.Random;

public class LuhnValidator {
    public static boolean luhnValidate(long number) {
        String digits = String.valueOf(number);
        int checksum = 0;
        boolean isEven = true;
        for (int i = digits.length() - 1; i >= 0; i--) {
            int digit = Character.getNumericValue(digits.charAt(i));
            if (isEven) {
                digit *= 2;
                if (digit > 9) digit -= 9;
            }
            checksum += digit;
            isEven = !isEven;
        }
        return checksum % 10 == 0;
    }

    public static long generateValidNumber(int length) {
        Random random = new Random();
        long[] digits = new long[length - 1];
        for (int i = 0; i < length - 1; i++) {
            digits[i] = random.nextInt(10);
        }
        long checksum = 0;
        for (int i = digits.length - 1; i >= 0; i--) {
            long digit = digits[i];
            if ((length - 1 - i) % 2 == 0) {
                digit *= 2;
                if (digit > 9) digit -= 9;
            }
            checksum += digit;
        }
        long checkDigit = (10 - (checksum % 10)) % 10;
        long result = 0;
        for (long digit : digits) {
            result = result * 10 + digit;
        }
        return result * 10 + checkDigit;
    }

    public static void main(String[] args) {
        System.out.println(luhnValidate(4532015112830366L));  // true
        System.out.println(luhnValidate(4532015112830367L));  // false
        System.out.println(generateValidNumber(16));  // Menghasilkan nombor 16-digit yang sah
    }
}

Kes Khas dan Pertimbangan

Apabila melaksanakan algoritma Luhn, pertimbangkan kes khas dan pertimbangan berikut:

1. Pengesahan Input: Pastikan bahawa input adalah rentetan nombor yang sah. Watak bukan digit harus ditangani dengan sewajarnya (sama ada dibuang atau dianggap sebagai input tidak sah).

2. Sifar Mula: Algoritma harus berfungsi dengan betul dengan nombor yang mempunyai sifar mula.

3. Nombor Besar: Bersedia untuk menangani nombor yang sangat panjang yang mungkin melebihi kapasiti jenis integer standard dalam beberapa bahasa pengaturcaraan.

4. Input Kosong: Tentukan bagaimana pelaksanaan anda harus menangani rentetan kosong atau input null.

5. Set Karakter Tidak Standard: Dalam beberapa aplikasi, anda mungkin menemui nombor yang diwakili dengan watak di luar julat standard 0-9. Tentukan bagaimana ini harus ditangani.

6. Pertimbangan Prestasi: Untuk aplikasi yang perlu mengesahkan sejumlah besar input dengan cepat, pertimbangkan untuk mengoptimumkan pelaksanaan algoritma.

Contoh Numerik

1. Nombor Kad Kredit Sah:

   • Nombor: 4532015112830366
   • Semakan Luhn: Sah

2. Nombor Kad Kredit Tidak Sah:

   • Nombor: 4532015112830367
   • Semakan Luhn: Tidak Sah

3. Nombor Insurans Sosial Kanada Sah:

   • Nombor: 046 454 286
   • Semakan Luhn: Sah

4. Nombor IMEI Tidak Sah:

   • Nombor: 490154203237518
   • Semakan Luhn: Tidak Sah

Kes Ujian

Untuk mengesahkan pelaksanaan algoritma Luhn, anda boleh menggunakan kes ujian berikut:

def test_luhn_algorithm():
    assert luhn_validate(4532015112830366) == True
    assert luhn_validate(4532015112830367) == False
    assert luhn_validate(79927398713) == True
    assert luhn_validate(79927398714) == False
    
    # Uji nombor yang dihasilkan
    for _ in range(10):
        assert luhn_validate(generate_valid_number(16)) == True
    
    print("Semua ujian lulus!")

test_luhn_algorithm()

Rujukan

1. Luhn, H. P. (1960). "Komputer untuk Mengesahkan Nombor". Paten AS 2,950,048.
2. Gallian, Joseph. "Matematik Nombor Pengenalan." Jurnal Matematik Kolej, vol. 22, no. 3, 1991, ms. 194–202. JSTOR, www.jstor.org/stable/2686878.
3. "ISO/IEC 7812-1:2017". Organisasi Standard Antarabangsa. Diambil pada 2 Ogos 2024.
4. Knuth, Donald. "Seni Pengaturcaraan Komputer, Jilid 2: Algoritma Seminumerik". Addison-Wesley, 1997.