Kalkulator algorytmu Luhna

Kalkulator Algorytmu Luhna

Wprowadzenie

Algorytm Luhna, znany również jako algorytm "moduł 10" lub "mod 10", to prosty wzór kontrolny używany do walidacji różnych numerów identyfikacyjnych, takich jak numery kart kredytowych, kanadyjskie numery ubezpieczenia społecznego, numery IMEI oraz numery identyfikacyjne dostawców w Stanach Zjednoczonych. Ten kalkulator pozwala na walidację numerów przy użyciu algorytmu Luhna oraz generowanie prawidłowych numerów, które przechodzą kontrolę Luhna.

Jak działa algorytm Luhna

Algorytm Luhna działa w następujący sposób:

Zaczynając od najbardziej prawej cyfry (z wyjątkiem cyfry kontrolnej) i przesuwając się w lewo, podwój wartość każdej drugiej cyfry.
Jeśli wynik tej operacji podwajania jest większy niż 9, odejmij 9 od wyniku.
Zsumuj wszystkie cyfry w powstałej sekwencji.
Jeśli suma modulo 10 jest równa 0 (jeśli suma kończy się zerem), to numer jest ważny zgodnie z wzorem Luhna; w przeciwnym razie nie jest ważny.

Oto wizualna reprezentacja algorytmu Luhna:

Wzór

Algorytm Luhna można wyrazić matematycznie w następujący sposób:

Niech $d_i$ będzie $i$ -tą cyfrą, licząc od najbardziej prawej cyfry (z wyjątkiem cyfry kontrolnej) i przesuwając się w lewo. Następnie cyfra kontrolna $d_0$ jest wybierana 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$

Gdzie $\bmod$ to operacja modulo.

Przykłady zastosowania

Algorytm Luhna ma różne zastosowania w różnych dziedzinach:

Walidacja kart kredytowych: Większość numerów kart kredytowych jest walidowana przy użyciu algorytmu Luhna.
Kanadyjskie numery ubezpieczenia społecznego: Algorytm Luhna jest używany do weryfikacji ważności tych numerów identyfikacyjnych.
Numery IMEI: Numery IMEI telefonów komórkowych zawierają cyfrę kontrolną walidowaną przez algorytm Luhna.
Numery identyfikacyjne dostawców (NPI): Używane w amerykańskim systemie opieki zdrowotnej, te numery są walidowane przy użyciu algorytmu Luhna.
ISBN: Niektóre numery ISBN-10 używają wariantu algorytmu Luhna do walidacji.

Alternatywy

Chociaż algorytm Luhna jest szeroko stosowany, istnieją inne algorytmy kontrolne do różnych celów:

Algorytm Damma: Inny algorytm cyfry kontrolnej, który wykrywa wszystkie błędy jednocyfrowe i wszystkie błędy transpozycyjne sąsiednich cyfr.
Algorytm Verhoeffa: Bardziej złożony algorytm kontrolny, który wykrywa wszystkie błędy jednocyfrowe i większość błędów transpozycyjnych.
Cyfra kontrolna ISBN-13: Używa innego algorytmu niż ISBN-10, który opiera się na algorytmie Luhna.

Historia

Algorytm Luhna został stworzony przez Hansa Petera Luhna, naukowca z IBM, w 1954 roku. Luhn był pionierem w dziedzinie nauki o informacji i jest uznawany za twórcę kilku innowacji, w tym systemu indeksowania KWIC (Key Word In Context).

Algorytm został pierwotnie zaprojektowany w celu ochrony przed przypadkowymi błędami, a nie atakami złośliwymi. Ważne jest, aby zauważyć, że chociaż algorytm Luhna może wykryć wiele powszechnych błędów, nie jest bezpieczną formą szyfrowania i nie powinien być wykorzystywany do celów bezpieczeństwa danych.

Pomimo swojego wieku, algorytm Luhna pozostaje szeroko stosowany ze względu na swoją prostotę i skuteczność w wychwytywaniu powszechnych błędów transkrypcyjnych.

Przykłady implementacji

Oto kilka przykładów kodu implementującego algorytm Luhna w różnych językach programowania:

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

## Przykład użycia:
print(luhn_validate(4532015112830366))  # True
print(luhn_validate(4532015112830367))  # False
print(generate_valid_number(16))  # Generuje prawidłowy 16-cyfrowy numer

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

// Przykład użycia:
console.log(luhnValidate(4532015112830366));  // true
console.log(luhnValidate(4532015112830367));  // false
console.log(generateValidNumber(16));  // Generuje prawidłowy 16-cyfrowy numer

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 prawidłowy 16-cyfrowy numer
    }
}

Przypadki brzegowe i specjalne uwagi

Podczas implementacji algorytmu Luhna, należy wziąć pod uwagę następujące przypadki brzegowe i specjalne uwagi:

Walidacja wejścia: Upewnij się, że wejście jest prawidłowym ciągiem numerycznym. Niekontrolowane znaki powinny być odpowiednio obsługiwane (usunięte lub traktowane jako nieprawidłowe wejście).
Zera wiodące: Algorytm powinien działać poprawnie z numerami, które mają zera wiodące.
Duże liczby: Bądź przygotowany na obsługę bardzo długich numerów, które mogą przekraczać pojemność standardowych typów całkowitych w niektórych językach programowania.
Puste wejście: Zdefiniuj, jak twoja implementacja powinna obsługiwać puste ciągi lub wartości null.
Niekontrolowane zestawy znaków: W niektórych aplikacjach możesz napotkać numery reprezentowane znakami spoza standardowego zakresu 0-9. Zdefiniuj, jak powinny być one obsługiwane.
Rozważania dotyczące wydajności: Dla aplikacji, które muszą szybko walidować dużą liczbę wejść, rozważ optymalizację implementacji algorytmu.

Przykłady numeryczne

Ważny numer karty kredytowej:
- Numer: 4532015112830366
- Kontrola Luhna: Ważny
Nieprawidłowy numer karty kredytowej:
- Numer: 4532015112830367
- Kontrola Luhna: Nieprawidłowy
Ważny kanadyjski numer ubezpieczenia społecznego:
- Numer: 046 454 286
- Kontrola Luhna: Ważny
Nieprawidłowy numer IMEI:
- Numer: 490154203237518
- Kontrola Luhna: Nieprawidłowy

Przypadki testowe

Aby zweryfikować implementację algorytmu Luhna, możesz użyć następujących przypadków testowych:

def test_luhn_algorithm():
    assert luhn_validate(4532015112830366) == True
    assert luhn_validate(4532015112830367) == False
    assert luhn_validate(79927398713) == True
    assert luhn_validate(79927398714) == False
    
    # Testowanie wygenerowanych numerów
    for _ in range(10):
        assert luhn_validate(generate_valid_number(16)) == True
    
    print("Wszystkie testy przeszły pomyślnie!")

test_luhn_algorithm()

Odniesienia

Luhn, H. P. (1960). "Computer for Verifying Numbers". US Patent 2,950,048.
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.
"ISO/IEC 7812-1:2017". Międzynarodowa Organizacja Normalizacyjna. Pobrano 2 sierpnia 2024.
Knuth, Donald. "The Art of Computer Programming, Volume 2: Seminumerical Algorithms". Addison-Wesley, 1997.