Luhn Algoritam Kalkulator

Uvod

Luhn algoritam, poznat i kao "modulus 10" ili "mod 10" algoritam, je jednostavna formula za kontrolni zbroj koja se koristi za validaciju raznih identifikacijskih brojeva, kao što su brojevi kreditnih kartica, kanadski brojevi socijalnog osiguranja, IMEI brojevi i brojevi nacionalnog pružatelja usluga u Sjedinjenim Američkim Državama. Ovaj kalkulator omogućuje vam da validirate brojeve koristeći Luhn algoritam i generirate važeće brojeve koji prolaze Luhn provjeru.

Kako Luhn Algoritam Radi

Luhn algoritam radi na sljedeći način:

1. Počevši od desnog krajnjeg broja (izuzimajući kontrolni broj) i krećući se lijevo, udvostručite vrijednost svakog drugog broja.
2. Ako je rezultat ove operacije udvostručavanja veći od 9, oduzmite 9 od rezultata.
3. Zbrojite sve brojeve u rezultantnom nizu.
4. Ako je ukupni zbroj modulo 10 jednak 0 (ako ukupni zbroj završava s nulom), tada je broj važeći prema Luhn formuli; inače, nije važeći.

Evo vizualne reprezentacije Luhn algoritma:

Formula

Luhn algoritam može se matematički izraziti na sljedeći način:

Neka $d_i$ bude $i$-ti broj, brojeći od desnog krajnjeg broja (izuzimajući kontrolni broj) i krećući se lijevo. Tada se kontrolni broj $d_0$ bira 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$

Gdje $\bmod$ predstavlja modulo operaciju.

Upotrebe

Luhn algoritam ima razne primjene u različitim područjima:

1. Validacija brojeva kreditnih kartica: Većina brojeva kreditnih kartica validira se koristeći Luhn algoritam.
2. Kanadski brojevi socijalnog osiguranja: Luhn algoritam se koristi za provjeru valjanosti ovih identifikacijskih brojeva.
3. IMEI brojevi: Brojevi mobilnih telefona IMEI uključuju kontrolni broj koji validira Luhn algoritam.
4. Brojevi nacionalnog pružatelja usluga (NPI): Koristi se u zdravstvenom sustavu Sjedinjenih Američkih Država, ovi brojevi se validiraju koristeći Luhn algoritam.
5. ISBN-ovi: Neki ISBN-10 brojevi koriste varijantu Luhn algoritma za validaciju.

Alternativa

Iako je Luhn algoritam široko korišten, postoje i drugi algoritmi za kontrolni zbroj za različite svrhe:

1. Damm algoritam: Još jedan algoritam za kontrolni broj koji otkriva sve greške s jednim brojem i sve greške susjednih transpozicija.
2. Verhoeff algoritam: Složeniji algoritam za kontrolni zbroj koji hvata sve greške s jednim brojem i većinu grešaka transpozicije.
3. ISBN-13 kontrolni broj: Koristi drugačiji algoritam od ISBN-10, koji se temelji na Luhn algoritmu.

Povijest

Luhn algoritam je stvorio Hans Peter Luhn, IBM-ov računalni znanstvenik, 1954. godine. Luhn je bio pionir u području informacijske znanosti i zaslužan je za nekoliko inovacija, uključujući KWIC (Key Word In Context) indeksni sustav.

Algoritam je prvotno dizajniran za zaštitu od slučajnih grešaka, a ne zlonamjernih napada. Važno je napomenuti da, iako Luhn algoritam može otkriti mnoge uobičajene greške, nije siguran oblik enkripcije i ne treba se oslanjati na njega za svrhe sigurnosti podataka.

Unatoč svojoj dobi, Luhn algoritam ostaje široko korišten zbog svoje jednostavnosti i učinkovitosti u otkrivanju uobičajenih grešaka pri prepisivanju.

Primjeri Implementacije

Evo nekoliko primjera koda za implementaciju Luhn algoritma na raznim programskim jezicima:

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## Primjer korištenja:
22print(luhn_validate(4532015112830366))  # True
23print(luhn_validate(4532015112830367))  # False
24print(generate_valid_number(16))  # Generira važeći 16-cifreni broj
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// Primjer korištenja:
29console.log(luhnValidate(4532015112830366));  // true
30console.log(luhnValidate(4532015112830367));  // false
31console.log(generateValidNumber(16));  // Generira važeći 16-cifreni broj
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 važeći 16-cifreni broj
47    }
48}
49

Rubne Situacije i Posebna Razmatranja

Kada implementirate Luhn algoritam, razmotrite sljedeće rubne situacije i posebna razmatranja:

1. Validacija Ulaza: Osigurajte da je ulaz važeći brojni niz. Ne-brojčani znakovi trebaju se pravilno obraditi (ili ukloniti ili tretirati kao nevažeći ulaz).

2. Vodeće Nule: Algoritam bi trebao ispravno raditi s brojevima koji imaju vodeće nule.

3. Veliki Brojevi: Budite spremni obraditi vrlo duge brojeve koji mogu premašiti kapacitet standardnih cjelobrojnih tipova u nekim programskim jezicima.

4. Prazan Ulaz: Definirajte kako vaša implementacija treba obraditi prazne nizove ili null ulaze.

5. Ne-standardni Skupovi Znakova: U nekim aplikacijama možete naići na brojeve predstavljene znakovima izvan standardnog raspona 0-9. Definirajte kako se oni trebaju obraditi.

6. Razmatranja Performansi: Za aplikacije koje trebaju brzo validirati velike brojeve unosa, razmotrite optimizaciju implementacije algoritma.

Numerički Primjeri

1. Važeći Broj Kreditne Kartice:

   • Broj: 4532015112830366
   • Luhn Provjera: Važeći

2. Nevažeći Broj Kreditne Kartice:

   • Broj: 4532015112830367
   • Luhn Provjera: Nevažeći

3. Važeći Kanadski Broj Socijalnog Osiguranja:

   • Broj: 046 454 286
   • Luhn Provjera: Važeći

4. Nevažeći IMEI Broj:

   • Broj: 490154203237518
   • Luhn Provjera: Nevažeći

Testni Slučajevi

Kako biste verificirali implementaciju Luhn algoritma, možete koristiti sljedeće testne slučajeve:

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 brojeve
8    for _ in range(10):
9        assert luhn_validate(generate_valid_number(16)) == True
10    
11    print("Svi testovi su prošli!")
12
13test_luhn_algorithm()
14

Reference

1. Luhn, H. P. (1960). "Računalo za Verifikaciju Brojeva". US Patent 2,950,048.
2. Gallian, Joseph. "Matematika Identifikacijskih Brojeva." The College Mathematics Journal, vol. 22, no. 3, 1991, pp. 194–202. JSTOR, www.jstor.org/stable/2686878.
3. "ISO/IEC 7812-1:2017". Međunarodna organizacija za standardizaciju. Preuzeto 2. kolovoza 2024.
4. Knuth, Donald. "Umijeće Računalnog Programiranja, Svezak 2: Polu-numerički Algoritmi". Addison-Wesley, 1997.