Kalkulator Luhnovega algoritma

Uvod

Luhnov algoritem, znan tudi kot "modulus 10" ali "mod 10" algoritem, je preprost kontrolni seštevek, ki se uporablja za preverjanje veljavnosti različnih identifikacijskih številk, kot so številke kreditnih kartic, kanadske številke socialne zavarovanja, IMEI številke in številke nacionalnih ponudnikov v Združenih državah. Ta kalkulator vam omogoča, da preverite številke z uporabo Luhnovega algoritma in generirate veljavne številke, ki prestanejo Luhnov test.

Kako deluje Luhnov algoritem

Luhnov algoritem deluje na naslednji način:

1. Začnite z desno najdeno številko (brez kontrolne številke) in se premikajte levo, podvojite vrednost vsake druge številke.
2. Če je rezultat te podvojitve večji od 9, odštejte 9 od rezultata.
3. Seštejte vse številke v nastali sekvenci.
4. Če je skupni znesek modulo 10 enak 0 (če se skupni znesek konča z ničlo), potem je številka veljavna po Luhnovi formuli; v nasprotnem primeru ni veljavna.

Tukaj je vizualna predstavitev Luhnovega algoritma:

Formula

Luhnov algoritem lahko matematično izrazimo takole:

Naj bo $d_i$ $i$-ta številka, šteto od desne (brez kontrolne številke) in se premikajoč levo. Nato je kontrolna številka $d_0$ izbrana tako, da:

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

Kjer $\bmod$ predstavlja modulo operacijo.

Uporabniški primeri

Luhnov algoritem ima različne aplikacije na različnih področjih:

1. Preverjanje številk kreditnih kartic: Večina številk kreditnih kartic se preverja z uporabo Luhnovega algoritma.
2. Kanadske številke socialne zavarovanja: Luhnov algoritem se uporablja za preverjanje veljavnosti teh identifikacijskih številk.
3. IMEI številke: Številke mobilnih telefonov IMEI vključujejo kontrolno številko, ki jo preverja Luhnov algoritem.
4. Številke nacionalnih ponudnikov (NPI): Uporabljene v zdravstvenem sistemu Združenih držav, te številke se preverjajo z Luhnovim algoritmom.
5. ISBN-ji: Nekatere številke ISBN-10 uporabljajo različico Luhnovega algoritma za preverjanje.

Alternativen

Čeprav je Luhnov algoritem široko uporabljen, obstajajo tudi drugi algoritmi za kontrolne številke za različne namene:

1. Dammov algoritem: Drug algoritem za kontrolne številke, ki zazna vse napake z eno številko in vse sosednje transpozicijske napake.
2. Verhoeffov algoritem: Kompleksnejši algoritem za kontrolne številke, ki zajame vse napake z eno številko in večino transpozicijskih napak.
3. Kontrolna številka ISBN-13: Uporablja drugačen algoritem kot ISBN-10, ki temelji na Luhnovem algoritmu.

Zgodovina

Luhnov algoritem je ustvaril Hans Peter Luhn, računalniški znanstvenik pri IBM-u, leta 1954. Luhn je bil pionir na področju informacijskih znanosti in je zaslužen za več inovacij, vključno s sistemom indeksiranja KWIC (Key Word In Context).

Algoritem je bil prvotno zasnovan za zaščito pred naključnimi napakami, ne pa zlonamernimi napadi. Pomembno je omeniti, da čeprav Luhnov algoritem lahko zazna mnoge pogoste napake, ni varen način šifriranja in se ne sme zanašati na varnost podatkov.

Kljub svoji starosti Luhnov algoritem ostaja široko uporabljen zaradi svoje preprostosti in učinkovitosti pri odkrivanju pogostih napak pri prepisovanju.

Primeri implementacije

Tukaj je nekaj primerov kode za implementacijo Luhnovega algoritma v različnih programskih jezikih:

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## Primer uporabe:
22print(luhn_validate(4532015112830366))  # True
23print(luhn_validate(4532015112830367))  # False
24print(generate_valid_number(16))  # Generira veljavno 16-mestno številko
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// Primer uporabe:
29console.log(luhnValidate(4532015112830366));  // true
30console.log(luhnValidate(4532015112830367));  // false
31console.log(generateValidNumber(16));  // Generira veljavno 16-mestno številko
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));  // Generira veljavno 16-mestno številko
47    }
48}
49

Robni primeri in posebne razmisleke

Pri implementaciji Luhnovega algoritma upoštevajte naslednje robne primere in posebne razmisleke:

1. Preverjanje vnosa: Poskrbite, da je vnos veljavna številčna niz. Neštevilski znaki naj se ustrezno obravnavajo (bodisi odstranijo bodisi obravnavajo kot neveljaven vnos).

2. Vodilne ničle: Algoritem bi moral pravilno delovati z številkami, ki imajo vodilne ničle.

3. Velike številke: Bodite pripravljeni obravnavati zelo dolge številke, ki bi lahko presegle kapaciteto standardnih celih tipov v nekaterih programskih jezikih.

4. Prazni vnosi: Določite, kako naj vaša implementacija obravnava prazne nize ali null vnose.

5. Ne-standardni nabori znakov: V nekaterih aplikacijah se lahko srečate s številkami, predstavljenimi z znaki zunaj standardnega obsega 0-9. Določite, kako naj se ti obravnavajo.

6. Razmisleki o zmogljivosti: Za aplikacije, ki morajo hitro preveriti veliko število vhodov, razmislite o optimizaciji implementacije algoritma.

Numerični primeri

1. Veljavna številka kreditne kartice:

   • Številka: 4532015112830366
   • Luhnova preveritev: Veljavna

2. Neveljavna številka kreditne kartice:

   • Številka: 4532015112830367
   • Luhnova preveritev: Neveljavna

3. Veljavna kanadska številka socialne zavarovanja:

   • Številka: 046 454 286
   • Luhnova preveritev: Veljavna

4. Neveljavna IMEI številka:

   • Številka: 490154203237518
   • Luhnova preveritev: Neveljavna

Testni primeri

Za preverjanje implementacije Luhnovega algoritma lahko uporabite naslednje testne primere:

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    # Testirajte generirane številke
8    for _ in range(10):
9        assert luhn_validate(generate_valid_number(16)) == True
10    
11    print("Vsi testi so uspešno opravili!")
12
13test_luhn_algorithm()
14

Reference

1. Luhn, H. P. (1960). "Računalnik za preverjanje številk". ZDA Patent 2,950,048.
2. Gallian, Joseph. "Matematika identifikacijskih številk." The College Mathematics Journal, vol. 22, št. 3, 1991, str. 194–202. JSTOR, www.jstor.org/stable/2686878.
3. "ISO/IEC 7812-1:2017". Mednarodna organizacija za standardizacijo. Pridobljeno 2. avgusta 2024.
4. Knuth, Donald. "Umetnost računalniškega programiranja, Količina 2: Seminumerični algoritmi". Addison-Wesley, 1997.