Luhn algoritam kalkulator

Uvod

Luhn algoritam, poznat i kao "modulus 10" ili "mod 10" algoritam, je jednostavna formula za kontrolni zbir koja se koristi za validaciju različitih identifikacionih brojeva, kao što su brojevi kreditnih kartica, kanadski brojevi socijalnog osiguranja, IMEI brojevi i brojevi nacionalnog pružatelja identiteta u Sjedinjenim Američkim Državama. Ovaj kalkulator vam omogućava da validirate brojeve koristeći Luhn algoritam i generišete validne brojeve koji prolaze Luhn proveru.

Kako Luhn algoritam funkcioniše

Luhn algoritam funkcioniše na sledeći način:

1. Počevši od desnog najudaljenijeg broja (izuzev kontrolnog broja) i krećući se levo, duplirajte vrednost svakog drugog broja.
2. Ako je rezultat ove operacije dupliranja veći od 9, oduzmite 9 od rezultata.
3. Saberite sve cifre u dobijenom nizu.
4. Ako je ukupni zbir modulo 10 jednak 0 (ako ukupni zbir završava sa nulom), tada je broj validan prema Luhn formuli; u suprotnom, nije validan.

Evo vizuelne reprezentacije Luhn algoritma:

Formula

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

Neka $d_i$ bude $i$-ta cifra, brojeći od desnog najudaljenijeg broja (izuzev kontrolnog broja) i krećući se levo. 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$

Gde $\bmod$ predstavlja modulo operaciju.

Upotreba

Luhn algoritam ima razne primene u različitim oblastima:

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

Alternative

Iako je Luhn algoritam široko korišćen, postoje i drugi algoritmi za kontrolni zbir za različite svrhe:

1. Damm algoritam: Još jedan algoritam za kontrolni broj koji otkriva sve greške sa jednim ciframa i sve greške u susednim transpozicijama.
2. Verhoeff algoritam: Složeniji algoritam za kontrolni zbir koji hvata sve greške sa jednim ciframa i većinu grešaka u transpoziciji.
3. ISBN-13 kontrolni broj: Koristi drugačiji algoritam od ISBN-10, koji se zasniva na Luhn algoritmu.

Istorija

Luhn algoritam je stvorio Hans Peter Luhn, IBM-ov informatičar, 1954. godine. Luhn je bio pionir u oblasti informacione nauke i zaslužan je za nekoliko inovacija, uključujući KWIC (Key Word In Context) indeksni sistem.

Algoritam je prvobitno dizajniran da zaštiti od slučajnih grešaka, a ne od zlonamernih napada. Važno je napomenuti da, iako Luhn algoritam može otkriti mnoge uobičajene greške, to nije siguran oblik enkripcije i ne bi se trebao oslanjati na njega za svrhe bezbednosti podataka.

Uprkos svom uzrastu, Luhn algoritam ostaje široko korišćen zbog svoje jednostavnosti i efikasnosti u hvatanju uobičajenih grešaka prilikom prepisivanja.

Primeri implementacije

Evo nekoliko primera koda za implementaciju Luhn algoritma na različitim 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## Primer korišćenja:
22print(luhn_validate(4532015112830366))  # True
23print(luhn_validate(4532015112830367))  # False
24print(generate_valid_number(16))  # Generiše validan 16-cifren 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// Primer korišćenja:
29console.log(luhnValidate(4532015112830366));  // true
30console.log(luhnValidate(4532015112830367));  // false
31console.log(generateValidNumber(16));  // Generiše validan 16-cifren 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));  // Generiše validan 16-cifren broj
47    }
48}
49

Ivicne situacije i posebna razmatranja

Kada implementirate Luhn algoritam, razmotrite sledeće ivicne situacije i posebna razmatranja:

1. Validacija ulaza: Osigurajte da je ulaz validan broj string. Ne-digitalni karakteri treba da budu pravilno obrađeni (ili uklonjeni ili tretirani kao nevalidan ulaz).

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

3. Veliki brojevi: Budite spremni da obradite vrlo duge brojeve koji mogu premašiti kapacitet standardnih celih tipova u nekim programskim jezicima.

4. Prazan ulaz: Definišite kako vaša implementacija treba da se nosi sa praznim stringovima ili null ulazima.

5. Ne-standardni skupovi karaktera: U nekim aplikacijama možete naići na brojeve predstavljene karakterima van standardnog opsega 0-9. Definišite kako bi se ovakvi trebali obraditi.

6. Razmatranja performansi: Za aplikacije koje trebaju brzo da validiraju veliki broj ulaza, razmotrite optimizaciju implementacije algoritma.

Numerički primeri

1. Validan broj kreditne kartice:

   • Broj: 4532015112830366
   • Luhn provera: Validan

2. Nevalidan broj kreditne kartice:

   • Broj: 4532015112830367
   • Luhn provera: Nevalidan

3. Validan kanadski broj socijalnog osiguranja:

   • Broj: 046 454 286
   • Luhn provera: Validan

4. Nevalidan IMEI broj:

   • Broj: 490154203237518
   • Luhn provera: Nevalidan

Test slučajevi

Da biste verifikovali implementaciju Luhn algoritma, možete koristiti sledeće test 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    # Test generisanih brojeva
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čunar za verifikaciju brojeva". US Patent 2,950,048.
2. Gallian, Joseph. "Matematika identifikacionih brojeva." The College Mathematics Journal, vol. 22, no. 3, 1991, str. 194–202. JSTOR, www.jstor.org/stable/2686878.
3. "ISO/IEC 7812-1:2017". Međunarodna organizacija za standardizaciju. Preuzeto 2. avgusta 2024.
4. Knuth, Donald. "Umjetnost programiranja računara, Tom 2: Polunumerički algoritmi". Addison-Wesley, 1997.