Kalkulačka Luhnova algoritmu

Kalkulátor Luhnova algoritmu

Úvod

Luhnův algoritmus, také známý jako algoritmus "modulus 10" nebo "mod 10", je jednoduchý kontrolní součet, který se používá k validaci různých identifikačních čísel, jako jsou čísla kreditních karet, kanadská čísla sociálního pojištění, IMEI čísla a čísla národního poskytovatele v USA. Tento kalkulátor vám umožňuje validovat čísla pomocí Luhnova algoritmu a generovat platná čísla, která projdou Luhnovou kontrolou.

Jak Luhnův algoritmus funguje

Luhnův algoritmus funguje následovně:

1. Začněte od pravého nejvíce číslice (s výjimkou kontrolní číslice) a pohybujte se vlevo, zdvojnásobte hodnotu každé druhé číslice.
2. Pokud je výsledek této operace zdvojení větší než 9, odečtěte 9 od výsledku.
3. Sečtěte všechny číslice v výsledné sekvenci.
4. Pokud je celkový součet modulo 10 roven 0 (pokud celkový součet končí nulou), pak je číslo platné podle Luhnova vzorce; jinak není platné.

Zde je vizuální znázornění Luhnova algoritmu:

Vzorec

Luhnův algoritmus lze matematicky vyjádřit takto:

Nechť $d_i$ je $i$-tá číslice, počítáno od pravé nejvíce číslice (s výjimkou kontrolní číslice) a pohybující se vlevo. Potom je kontrolní číslice $d_0$ vybrána 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 operace.

Případové použití

Luhnův algoritmus má různé aplikace v různých oblastech:

1. Validace čísel kreditních karet: Většina čísel kreditních karet je validována pomocí Luhnova algoritmu.
2. Kanadská čísla sociálního pojištění: Luhnův algoritmus se používá k ověření platnosti těchto identifikačních čísel.
3. IMEI čísla: Čísla IMEI mobilních telefonů obsahují kontrolní číslici validovanou Luhnovým algoritmem.
4. Čísla národního poskytovatele (NPI): Používají se ve zdravotnickém systému USA, tato čísla jsou validována pomocí Luhnova algoritmu.
5. ISBN: Některá čísla ISBN-10 používají variantu Luhnova algoritmu pro validaci.

Alternativy

I když je Luhnův algoritmus široce používán, existují i jiné algoritmy kontrolního součtu pro různé účely:

1. Dammův algoritmus: Další algoritmus kontrolní číslice, který detekuje všechny jednociferné chyby a všechny sousední transpoziční chyby.
2. Verhoeffův algoritmus: Složitější algoritmus kontrolního součtu, který zachycuje všechny jednociferné chyby a většinu transpozičních chyb.
3. Kontrolní číslice ISBN-13: Používá jiný algoritmus než ISBN-10, který je založen na Luhnově algoritmu.

Historie

Luhnův algoritmus vytvořil Hans Peter Luhn, počítačový vědec z IBM, v roce 1954. Luhn byl průkopníkem v oblasti informační vědy a je přičítán několika inovacím, včetně systému indexování KWIC (Key Word In Context).

Algoritmus byl původně navržen k ochraně proti náhodným chybám, nikoli proti zlým útokům. Je důležité poznamenat, že i když Luhnův algoritmus může detekovat mnoho běžných chyb, není bezpečnou formou šifrování a neměl by být spolehlivě používán pro účely zabezpečení dat.

Navzdory svému věku zůstává Luhnův algoritmus široce používán díky své jednoduchosti a účinnosti při zachycování běžných chyb při přepisu.

Příklady implementace

Zde jsou některé příklady kódu pro implementaci Luhnova algoritmu v různých programovacích jazycích:

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])))

## Příklad použití:
print(luhn_validate(4532015112830366))  # True
print(luhn_validate(4532015112830367))  # False
print(generate_valid_number(16))  # Generuje platné 16-ciferné číslo

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);
}

// Příklad použití:
console.log(luhnValidate(4532015112830366));  // true
console.log(luhnValidate(4532015112830367));  // false
console.log(generateValidNumber(16));  // Generuje platné 16-ciferné číslo

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));  // Generuje platné 16-ciferné číslo
    }
}

Okrajové případy a zvláštní úvahy

Při implementaci Luhnova algoritmu zvažte následující okrajové případy a zvláštní úvahy:

1. Validace vstupu: Zajistěte, aby byl vstup platným číselným řetězcem. Nečíselné znaky by měly být zpracovány vhodně (buď odstraněny, nebo považovány za neplatný vstup).

2. Počáteční nuly: Algoritmus by měl správně fungovat s čísly, která mají počáteční nuly.

3. Velká čísla: Buďte připraveni zpracovat velmi dlouhá čísla, která mohou překročit kapacitu standardních celočíselných typů v některých programovacích jazycích.

4. Prázdný vstup: Definujte, jak by vaše implementace měla zpracovat prázdné řetězce nebo null vstupy.

5. Nestandardní znakové sady: V některých aplikacích můžete narazit na čísla reprezentovaná znaky mimo standardní rozsah 0-9. Definujte, jak by měla být tato čísla zpracována.

6. Úvahy o výkonu: Pro aplikace, které potřebují rychle validovat velké množství vstupů, zvažte optimalizaci implementace algoritmu.

Číselné příklady

1. Platné číslo kreditní karty:

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

2. Neplatné číslo kreditní karty:

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

3. Platné kanadské číslo sociálního pojištění:

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

4. Neplatné číslo IMEI:

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

Testovací případy

Pro ověření implementace Luhnova algoritmu můžete použít následující testovací případy:

def test_luhn_algorithm():
    assert luhn_validate(4532015112830366) == True
    assert luhn_validate(4532015112830367) == False
    assert luhn_validate(79927398713) == True
    assert luhn_validate(79927398714) == False
    
    # Test generovaných čísel
    for _ in range(10):
        assert luhn_validate(generate_valid_number(16)) == True
    
    print("Všechny testy prošly!")

test_luhn_algorithm()

Odkazy

1. Luhn, H. P. (1960). "Computer for Verifying Numbers". US Patent 2,950,048.
2. Gallian, Joseph. "The Mathematics of Identification Numbers." The College Mathematics Journal, vol. 22, no. 3, 1991, pp. 194–202. JSTOR, www.jstor.org/stable/2686878.
3. "ISO/IEC 7812-1:2017". International Organization for Standardization. Retrieved August 2, 2024.
4. Knuth, Donald. "The Art of Computer Programming, Volume 2: Seminumerical Algorithms". Addison-Wesley, 1997.