Luhni algoritmi kalkulaator

Luhn'i algoritmi kalkulaator

Sissejuhatus

Luhn'i algoritm, tuntud ka kui "modulus 10" või "mod 10" algoritm, on lihtne kontrollsumma valem, mida kasutatakse erinevate identifitseerimisnumberite valideerimiseks, nagu krediitkaardi numbrid, Kanada sotsiaalkindlustuse numbrid, IMEI numbrid ja riiklikud pakkuja identifikaatori numbrid Ameerika Ühendriikides. See kalkulaator võimaldab teil valideerida numbreid Luhn'i algoritmi abil ja genereerida kehtivaid numbreid, mis läbivad Luhn'i kontrolli.

Kuidas Luhn'i algoritm töötab

Luhn'i algoritm töötab järgmiselt:

1. Alustades parempoolsest numbrist (ilma kontrollnumbrita) ja liikudes vasakule, kahekordista iga teise numbri väärtus.
2. Kui selle kahekordistamise tulemuseks on rohkem kui 9, lahuta 9 tulemusele.
3. Summeerige kõik numbrid saadud järjestuses.
4. Kui summa modulo 10 on võrdne 0 (kui summa lõpeb nulliga), siis on number Luhn'i valemi kohaselt kehtiv; vastasel juhul ei ole see kehtiv.

Siin on visuaalne esitus Luhn'i algoritmist:

Valem

Luhn'i algoritmi saab matemaatiliselt väljendada järgmiselt:

Olgu $d_i$ $i$-ne number, loendades paremalt (ilma kontrollnumbrita) ja liikudes vasakule. Siis valitakse kontrollnumber $d_0$ nii, et:

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

Kus $\bmod$ on modulo operatsioon.

Kasutusalad

Luhn'i algoritmil on erinevaid rakendusi erinevates valdkondades:

1. Krediitkaardi valideerimine: Enamik krediitkaardi numbreid valideeritakse Luhn'i algoritmi abil.
2. Kanada sotsiaalkindlustuse numbrid: Luhn'i algoritmi kasutatakse nende identifitseerimisnumberite kehtivuse kontrollimiseks.
3. IMEI numbrid: Mobiiltelefonide IMEI numbrid sisaldavad kontrollnumbrit, mille valideerib Luhn'i algoritm.
4. Riiklikud pakkuja identifikaatori (NPI) numbrid: Ameerika Ühendriikide tervishoiusüsteemis kasutatakse neid numbreid Luhn'i algoritmi abil valideerimiseks.
5. ISBN-id: Mõned ISBN-10 numbrid kasutavad valideerimiseks Luhn'i algoritmi varianti.

Alternatiivid

Kuigi Luhn'i algoritm on laialdaselt kasutusel, on olemas ka teisi kontrollsumma algoritme erinevateks eesmärkideks:

1. Damm'i algoritm: Teine kontrollnumbrite algoritm, mis tuvastab kõik ühekohalised vead ja kõik külgnevate vahetuste vead.
2. Verhoeff'i algoritm: Kompleksem kontrollsumma algoritm, mis tuvastab kõik ühekohalised vead ja enamik vahetusvigu.
3. ISBN-13 kontrollnumber: Kasutab erinevat algoritmi kui ISBN-10, mis põhineb Luhn'i algoritmil.

Ajalugu

Luhn'i algoritmi lõi Hans Peter Luhn, IBM-i arvutiteadlane, 1954. aastal. Luhn oli teabe teaduse valdkonna pioneer ja talle kuulub mitmeid uuendusi, sealhulgas KWIC (Key Word In Context) indekseerimissüsteem.

Algoritm loodi algselt, et kaitsta juhuslike vigade eest, mitte pahatahtlike rünnakute eest. Oluline on märkida, et kuigi Luhn'i algoritm suudab tuvastada paljusid tavalisi vigu, ei ole see turvaline krüpteerimise vorm ja sellele ei tohiks toetuda andmete turvalisuse eesmärkidel.

Oma vanusest hoolimata jääb Luhn'i algoritm laialdaselt kasutusele oma lihtsuse ja efektiivsuse tõttu tavaliste transkriptsioonivigade tuvastamisel.

Rakendamise näited

Siin on mõned koodinäited Luhn'i algoritmi rakendamiseks erinevates programmeerimiskeeltes:

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

## Näide kasutamisest:
print(luhn_validate(4532015112830366))  # True
print(luhn_validate(4532015112830367))  # False
print(generate_valid_number(16))  # Genereerib kehtiva 16-kohalise numbri

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

// Näide kasutamisest:
console.log(luhnValidate(4532015112830366));  // true
console.log(luhnValidate(4532015112830367));  // false
console.log(generateValidNumber(16));  // Genereerib kehtiva 16-kohalise numbri

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));  // Genereerib kehtiva 16-kohalise numbri
    }
}

Äärmuslikud juhtumid ja erilised kaalutlused

Luhn'i algoritmi rakendamisel arvestage järgmiste äärmuslike juhtumite ja eriküsimustega:

1. Sisendi valideerimine: Veenduge, et sisend on kehtiv numbrirea. Mitte-numbrilised sümbolid tuleks käsitleda sobivalt (kas eemaldada või käsitleda kehtetuna).

2. Esialgsed nullid: Algoritm peaks õigesti töötama numbritega, millel on esialgsed nullid.

3. Suured numbrid: Olge valmis käsitlema väga pikki numbreid, mis võivad ületada mõnede programmeerimiskeelte standardsete täisarvutüüpide võimekuse.

4. Tühi sisend: Määratlege, kuidas teie rakendus peaks käsitlema tühje stringe või nullsisendeid.

5. Mitte-standardsete sümbolite kogumid: Mõnes rakenduses võite kokku puutuda numbritega, mis on esitatud sümbolitega väljaspool standardset 0-9 vahemikku. Määratlege, kuidas nende suhtes käituda.

6. Tootlikkuse kaalutlused: Rakenduste puhul, mis peavad kiiresti valideerima suures koguses sisendeid, kaaluge algoritmi rakenduse optimeerimist.

Numbrilised näited

1. Kehtiv krediitkaardi number:

   • Number: 4532015112830366
   • Luhn'i kontroll: Kehtiv

2. Kehtetu krediitkaardi number:

   • Number: 4532015112830367
   • Luhn'i kontroll: Kehtetu

3. Kehtiv Kanada sotsiaalkindlustuse number:

   • Number: 046 454 286
   • Luhn'i kontroll: Kehtiv

4. Kehtetu IMEI number:

   • Number: 490154203237518
   • Luhn'i kontroll: Kehtetu

Testjuhtumid

Luhn'i algoritmi rakenduse kontrollimiseks võite kasutada järgmisi testjuhtumeid:

def test_luhn_algorithm():
    assert luhn_validate(4532015112830366) == True
    assert luhn_validate(4532015112830367) == False
    assert luhn_validate(79927398713) == True
    assert luhn_validate(79927398714) == False
    
    # Testige genereeritud numbreid
    for _ in range(10):
        assert luhn_validate(generate_valid_number(16)) == True
    
    print("Kõik testid läbitud!")

test_luhn_algorithm()

Viidatud allikad

1. Luhn, H. P. (1960). "Arvuti numbrite kontrollimiseks". USA patent 2,950,048.
2. Gallian, Joseph. "Identifitseerimisnumberite matemaatika." College Mathematics Journal, vol. 22, nr. 3, 1991, lk. 194–202. JSTOR, www.jstor.org/stable/2686878.
3. "ISO/IEC 7812-1:2017". Rahvusvaheline standardiorganisatsioon. Juurdepääs 2. august 2024.
4. Knuth, Donald. "Arvutitehnika kunst, köide 2: Seminumerilised algoritmid". Addison-Wesley, 1997.