Luhn-algoritmin laskin

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ä:

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

## Esimerkkikäyttö:
print(luhn_validate(4532015112830366))  # True
print(luhn_validate(4532015112830367))  # False
print(generate_valid_number(16))  # Generoi voimassa olevan 16-numeroisen numeron

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

// Esimerkkikäyttö:
console.log(luhnValidate(4532015112830366));  // true
console.log(luhnValidate(4532015112830367));  // false
console.log(generateValidNumber(16));  // Generoi voimassa olevan 16-numeroisen numeron

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));  // Generoi voimassa olevan 16-numeroisen numeron
    }
}

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:

def test_luhn_algorithm():
    assert luhn_validate(4532015112830366) == True
    assert luhn_validate(4532015112830367) == False
    assert luhn_validate(79927398713) == True
    assert luhn_validate(79927398714) == False
    
    # Testaa luotuja numeroita
    for _ in range(10):
        assert luhn_validate(generate_valid_number(16)) == True
    
    print("Kaikki testit läpäisty!")

test_luhn_algorithm()

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.