Kalkulátor Luhnovho algoritmu

Úvod

Luhnov algoritmus, známy aj ako "modulus 10" alebo "mod 10" algoritmus, je jednoduchý kontrolný súčet používaný na validáciu rôznych identifikačných čísel, ako sú čísla kreditných kariet, kanadské čísla sociálneho zabezpečenia, IMEI čísla a čísla národného poskytovateľa identifikátorov v Spojených štátoch. Tento kalkulátor vám umožňuje validovať čísla pomocou Luhnovho algoritmu a generovať platné čísla, ktoré prechádzajú Luhnovou kontrolou.

Ako funguje Luhnov algoritmus

Luhnov algoritmus funguje nasledovne:

1. Začnite od pravého najviac čísla (s výnimkou kontrolného čísla) a pohybujte sa doľava, zdvojnásobte hodnotu každého druhého čísla.
2. Ak je výsledok tejto operácie zdvojnásobenia väčší ako 9, odpočítajte 9 od výsledku.
3. Sčítajte všetky číslice v výslednej sekvencii.
4. Ak je celkový súčet modulo 10 rovný 0 (ak celkový súčet končí nulou), potom je číslo platné podľa Luhnovej formulácie; inak nie je platné.

Tu je vizuálna reprezentácia Luhnovho algoritmu:

Formula

Luhnov algoritmus môže byť matematicky vyjadrený nasledovne:

Nech $d_i$ je $i$-tá číslica, počítajúc od pravého najviac čísla (s výnimkou kontrolného čísla) a pohybujúc sa doľava. Potom je kontrolná číslica $d_0$ vybraná tak, aby:

$(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$

Kde $\bmod$ je modulo operácia.

Použitie

Luhnov algoritmus má rôzne aplikácie v rôznych oblastiach:

1. Validácia kreditných kariet: Väčšina čísel kreditných kariet je validovaná pomocou Luhnovho algoritmu.
2. Kanadské čísla sociálneho zabezpečenia: Luhnov algoritmus sa používa na overenie platnosti týchto identifikačných čísel.
3. IMEI čísla: Čísla IMEI mobilných telefónov obsahujú kontrolnú číslicu, ktorú validuje Luhnov algoritmus.
4. Čísla národného poskytovateľa (NPI): Používané v americkom zdravotníckom systéme, tieto čísla sú validované pomocou Luhnovho algoritmu.
5. ISBN: Niektoré čísla ISBN-10 používajú variant Luhnoveho algoritmu na validáciu.

Alternatívy

Hoci je Luhnov algoritmus široko používaný, existujú aj iné algoritmy kontrolného súčtu na rôzne účely:

1. Dammov algoritmus: Ďalší algoritmus kontrolnej číslice, ktorý detekuje všetky jednociferné chyby a všetky susedné transpozičné chyby.
2. Verhoeffov algoritmus: Zložitejší algoritmus kontrolného súčtu, ktorý zachytáva všetky jednociferné chyby a väčšinu transpozičných chýb.
3. Kontrolná číslica ISBN-13: Používa iný algoritmus ako ISBN-10, ktorý je založený na Luhnovom algoritme.

História

Luhnov algoritmus vytvoril Hans Peter Luhn, počítačový vedec z IBM, v roku 1954. Luhn bol priekopníkom v oblasti informačnej vedy a je známy množstvom inovácií, vrátane systému indexovania KWIC (Kľúčové slová v kontexte).

Algoritmus bol pôvodne navrhnutý na ochranu proti náhodným chybám, nie na zlé útoky. Je dôležité poznamenať, že hoci Luhnov algoritmus dokáže detekovať mnohé bežné chyby, nie je to bezpečná forma šifrovania a nemal by sa spoliehať na účely zabezpečenia údajov.

Napriek svojmu veku zostáva Luhnov algoritmus široko používaný vďaka svojej jednoduchosti a účinnosti pri zachytávaní bežných prepisovacích chýb.

Implementačné príklady

Tu sú niektoré príklady kódu na implementáciu Luhnovho algoritmu v rôznych programovacích jazykoch:

1import random
2
3def luhn_validate(number):
4    digits = [int(d) for d in str(number)]
5    checksum = 0
6    for i in range(len(digits) - 1, -1, -1):
7        d = digits[i]
8        if (len(digits) - i) % 2 == 0:
9            d = d * 2
10            if d > 9:
11                d -= 9
12        checksum += d
13    return checksum % 10 == 0
14
15def generate_valid_number(length):
16    digits = [random.randint(0, 9) for _ in range(length - 1)]
17    checksum = sum(digits[::2]) + sum(sum(divmod(d * 2, 10)) for d in digits[-2::-2])
18    check_digit = (10 - (checksum % 10)) % 10
19    return int(''.join(map(str, digits + [check_digit])))
20
21## Príklad použitia:
22print(luhn_validate(4532015112830366))  # True
23print(luhn_validate(4532015112830367))  # False
24print(generate_valid_number(16))  # Generuje platné 16-ciferné číslo
25

1function luhnValidate(number) {
2    const digits = number.toString().split('').map(Number);
3    let checksum = 0;
4    for (let i = digits.length - 1; i >= 0; i--) {
5        let d = digits[i];
6        if ((digits.length - i) % 2 === 0) {
7            d *= 2;
8            if (d > 9) d -= 9;
9        }
10        checksum += d;
11    }
12    return checksum % 10 === 0;
13}
14
15function generateValidNumber(length) {
16    const digits = Array.from({length: length - 1}, () => Math.floor(Math.random() * 10));
17    const checksum = digits.reduce((sum, digit, index) => {
18        if ((length - 1 - index) % 2 === 0) {
19            digit *= 2;
20            if (digit > 9) digit -= 9;
21        }
22        return sum + digit;
23    }, 0);
24    const checkDigit = (10 - (checksum % 10)) % 10;
25    return parseInt(digits.join('') + checkDigit);
26}
27
28// Príklad použitia:
29console.log(luhnValidate(4532015112830366));  // true
30console.log(luhnValidate(4532015112830367));  // false
31console.log(generateValidNumber(16));  // Generuje platné 16-ciferné číslo
32

1import java.util.Random;
2
3public class LuhnValidator {
4    public static boolean luhnValidate(long number) {
5        String digits = String.valueOf(number);
6        int checksum = 0;
7        boolean isEven = true;
8        for (int i = digits.length() - 1; i >= 0; i--) {
9            int digit = Character.getNumericValue(digits.charAt(i));
10            if (isEven) {
11                digit *= 2;
12                if (digit > 9) digit -= 9;
13            }
14            checksum += digit;
15            isEven = !isEven;
16        }
17        return checksum % 10 == 0;
18    }
19
20    public static long generateValidNumber(int length) {
21        Random random = new Random();
22        long[] digits = new long[length - 1];
23        for (int i = 0; i < length - 1; i++) {
24            digits[i] = random.nextInt(10);
25        }
26        long checksum = 0;
27        for (int i = digits.length - 1; i >= 0; i--) {
28            long digit = digits[i];
29            if ((length - 1 - i) % 2 == 0) {
30                digit *= 2;
31                if (digit > 9) digit -= 9;
32            }
33            checksum += digit;
34        }
35        long checkDigit = (10 - (checksum % 10)) % 10;
36        long result = 0;
37        for (long digit : digits) {
38            result = result * 10 + digit;
39        }
40        return result * 10 + checkDigit;
41    }
42
43    public static void main(String[] args) {
44        System.out.println(luhnValidate(4532015112830366L));  // true
45        System.out.println(luhnValidate(4532015112830367L));  // false
46        System.out.println(generateValidNumber(16));  // Generuje platné 16-ciferné číslo
47    }
48}
49

Okrajové prípady a špeciálne úvahy

Pri implementácii Luhnovho algoritmu zvážte nasledujúce okrajové prípady a špeciálne úvahy:

1. Validácia vstupu: Uistite sa, že vstup je platný reťazec čísiel. Nečíselné znaky by mali byť spracované primerane (buď odstránené, alebo považované za neplatný vstup).

2. Vedúce nuly: Algoritmus by mal správne fungovať s číslami, ktoré majú vedúce nuly.

3. Veľké čísla: Buďte pripravení spracovať veľmi dlhé čísla, ktoré môžu presiahnuť kapacitu štandardných celočíselných typov v niektorých programovacích jazykoch.

4. Prázdny vstup: Definujte, ako by mala vaša implementácia spracovať prázdne reťazce alebo null vstupy.

5. Neštandardné znakové sady: V niektorých aplikáciách môžete naraziť na čísla reprezentované znakmi mimo štandardného rozsahu 0-9. Definujte, ako by sa s nimi malo zaobchádzať.

6. Úvahy o výkonnosti: Pre aplikácie, ktoré potrebujú rýchlo validovať veľké množstvo vstupov, zvážte optimalizáciu implementácie algoritmu.

Číselné príklady

1. Platné číslo kreditnej karty:

   • Číslo: 4532015112830366
   • Luhnova kontrola: Platné

2. Neplatné číslo kreditnej karty:

   • Číslo: 4532015112830367
   • Luhnova kontrola: Neplatné

3. Platné kanadské číslo sociálneho zabezpečenia:

   • Číslo: 046 454 286
   • Luhnova kontrola: Platné

4. Neplatné IMEI číslo:

   • Číslo: 490154203237518
   • Luhnova kontrola: Neplatné

Testovacie prípady

Na overenie implementácie Luhnovho algoritmu môžete použiť nasledujúce testovacie prípady:

1def test_luhn_algorithm():
2    assert luhn_validate(4532015112830366) == True
3    assert luhn_validate(4532015112830367) == False
4    assert luhn_validate(79927398713) == True
5    assert luhn_validate(79927398714) == False
6    
7    # Test generovaných čísel
8    for _ in range(10):
9        assert luhn_validate(generate_valid_number(16)) == True
10    
11    print("Všetky testy prešli!")
12
13test_luhn_algorithm()
14

Odkazy

1. Luhn, H. P. (1960). "Počítač na overovanie čísel". US Patent 2,950,048.
2. Gallian, Joseph. "Matematika identifikačných čísel." The College Mathematics Journal, vol. 22, no. 3, 1991, pp. 194–202. JSTOR, www.jstor.org/stable/2686878.
3. "ISO/IEC 7812-1:2017". Medzinárodná organizácia pre normalizáciu. Získané 2. augusta 2024.
4. Knuth, Donald. "Umenie počítačového programovania, Zväzok 2: Seminumerické algoritmy". Addison-Wesley, 1997.