Luhn-algoritmin laskin

Johdanto

Luhn-algoritmi, joka tunnetaan myös nimellä "modulus 10" tai "mod 10" algoritmi, on yksinkertainen tarkistussumma, jota käytetään erilaisten tunnistenumeroiden, kuten luottokorttinumeroiden, Kanadan sosiaaliturvatunnusten, IMEI-numeroiden ja Yhdysvaltojen kansallisten palveluntarjoajatunnusten validoimiseen. Tämä laskin mahdollistaa numeroiden validoimisen Luhn-algoritmin avulla ja luo voimassa olevia numeroita, jotka läpäisevät Luhn-tarkistuksen.

Kuinka Luhn-algoritmi toimii

Luhn-algoritmi toimii seuraavasti:

1. Aloita oikeasta reunasta (ilman tarkistussummaa) ja siirry vasemmalle, kaksinkertaista jokaisen toisen numeron arvo.
2. Jos tämän kaksinkertaistamisen tulos on suurempi kuin 9, vähennä tuloksesta 9.
3. Laske yhteen kaikki numerot tuloksena olevassa sekvenssissä.
4. Jos kokonaismäärä modulo 10 on yhtä suuri kuin 0 (jos kokonaismäärä päättyy nollaan), niin numero on voimassa Luhn-kaavan mukaan; muuten se ei ole voimassa.

Tässä on visuaalinen esitys Luhn-algoritmista:

Kaava

Luhn-algoritmi voidaan ilmaista matemaattisesti seuraavasti:

Olkoon $d_i$ $i$:s numero, laskien oikeasta reunasta (ilman tarkistussummaa) ja siirtyen vasemmalle. Sitten tarkistussumma $d_0$ valitaan niin, että:

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

Missä $\bmod$ on modulo-operaatio.

Käyttötapaukset

Luhn-algoritmilla on erilaisia sovelluksia eri aloilla:

1. Luottokorttien validoiminen: Useimmat luottokorttinumerot validoidaan Luhn-algoritmin avulla.
2. Kanadan sosiaaliturvatunnukset: Luhn-algoritmia käytetään näiden tunnistenumeroiden voimassaolon tarkistamiseen.
3. IMEI-numerot: Matkapuhelinten IMEI-numerot sisältävät tarkistussumman, jonka Luhn-algoritmi validoi.
4. Kansalliset palveluntarjoajatunnukset (NPI): Yhdysvaltojen terveydenhuoltojärjestelmässä käytettävät numerot validoidaan Luhn-algoritmin avulla.
5. ISBN: Jotkut ISBN-10 numerot käyttävät Luhn-algoritmin muunnelmaa validoimiseen.

Vaihtoehdot

Vaikka Luhn-algoritmi on laajalti käytössä, on olemassa muita tarkistussumma-algoritmeja eri tarkoituksiin:

1. Damm-algoritmi: Toinen tarkistussumma-algoritmi, joka havaitsee kaikki yksittäiset virheet ja kaikki vierekkäiset transpositio-virheet.
2. Verhoeff-algoritmi: Monimutkaisempi tarkistussumma-algoritmi, joka havaitsee kaikki yksittäiset virheet ja useimmat transpositio-virheet.
3. ISBN-13 tarkistussumma: Käyttää eri algoritmia kuin ISBN-10, joka perustuu Luhn-algoritmiin.

Historia

Luhn-algoritmi luotiin Hans Peter Luhn'in, IBM:n tietojenkäsittelytieteen asiantuntijan, toimesta vuonna 1954. Luhn oli tietojenkäsittelytieteen pioneer, ja hänet tunnetaan useista innovaatioista, mukaan lukien KWIC (Key Word In Context) -indeksointijärjestelmä.

Algoritmi suunniteltiin alun perin suojaamaan vahingossa tapahtuvilta virheiltä, ei pahantahtoisilta hyökkäyksiltä. On tärkeää huomata, että vaikka Luhn-algoritmi voi havaita monia yleisiä virheitä, se ei ole turvallinen salausmuoto, eikä sitä tule käyttää tietoturvatarkoituksiin.

Huolimatta iästään, Luhn-algoritmi on edelleen laajalti käytössä sen yksinkertaisuuden ja tehokkuuden vuoksi yleisten kirjoitusvirheiden havaitsemisessa.

Toteutus Esimerkkejä

Tässä on joitakin koodiesimerkkejä Luhn-algoritmin toteuttamisesta eri ohjelmointikielillä:

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## Esimerkkikäyttö:
22print(luhn_validate(4532015112830366))  # True
23print(luhn_validate(4532015112830367))  # False
24print(generate_valid_number(16))  # Generoi voimassa olevan 16-numeroisen numeron
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// Esimerkkikäyttö:
29console.log(luhnValidate(4532015112830366));  // true
30console.log(luhnValidate(4532015112830367));  // false
31console.log(generateValidNumber(16));  // Generoi voimassa olevan 16-numeroisen numeron
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));  // Generoi voimassa olevan 16-numeroisen numeron
47    }
48}
49

Reunaehdot ja erityiset huomautukset

Luhn-algoritmin toteuttamisessa on syytä ottaa huomioon seuraavat reunaehdot ja erityiset huomautukset:

1. Syötteen validoiminen: Varmista, että syöte on voimassa oleva numerosarja. Ei-numeromerkit tulee käsitellä asianmukaisesti (joko poistaa tai käsitellä virheellisinä).

2. Johtavat nollat: Algoritmin tulisi toimia oikein numeroilla, joilla on johtavia nollia.

3. Suuret numerot: Ole valmis käsittelemään erittäin pitkiä numeroita, jotka saattavat ylittää joidenkin ohjelmointikielten standardien kokonaislukutyyppien kapasiteetin.

4. Tyhjät syötteet: Määritä, miten toteutuksesi tulisi käsitellä tyhjiä merkkijonoja tai nollasyötteitä.

5. Ei-standardit merkistöt: Joissakin sovelluksissa saatat kohdata numeroita, jotka on esitetty merkkeillä, jotka ovat standardin 0-9 ulkopuolella. Määritä, miten näitä tulisi käsitellä.

6. Suorituskykyhuomiot: Sovelluksille, jotka tarvitsevat suuren määrän syötteiden validoimista nopeasti, harkitse algoritmin toteutuksen optimointia.

Numeraaliset esimerkit

1. Voimassa oleva luottokorttinumero:

   • Numero: 4532015112830366
   • Luhn-tarkistus: Voimassa

2. Voimassa oleva luottokorttinumero:

   • Numero: 4532015112830367
   • Luhn-tarkistus: Ei voimassa

3. Voimassa oleva Kanadan sosiaaliturvatunnus:

   • Numero: 046 454 286
   • Luhn-tarkistus: Voimassa

4. Voimassa oleva IMEI-numero:

   • Numero: 490154203237518
   • Luhn-tarkistus: Ei voimassa

Testitapaukset

Varmistaaksesi Luhn-algoritmin toteutuksen voit käyttää seuraavia testitapauksia:

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    # Testaa luotuja numeroita
8    for _ in range(10):
9        assert luhn_validate(generate_valid_number(16)) == True
10    
11    print("Kaikki testit läpäisty!")
12
13test_luhn_algorithm()
14

Viitteet

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". Kansainvälinen standardointijärjestö. Haettu 2. elokuuta 2024.
4. Knuth, Donald. "The Art of Computer Programming, Volume 2: Seminumerical Algorithms". Addison-Wesley, 1997.