Luhno algoritmo skaičiuoklė

Luhn algoritmo skaičiuoklė

Įvadas

Luhn algoritmas, dar žinomas kaip "modulio 10" arba "mod 10" algoritmas, yra paprasta kontrolinė suma, naudojama įvairių identifikavimo numerių, tokių kaip kreditinių kortelių numeriai, Kanados socialinio draudimo numeriai, IMEI numeriai ir nacionaliniai teikėjų identifikavimo numeriai JAV, patvirtinimui. Ši skaičiuoklė leidžia jums patvirtinti numerius naudojant Luhn algoritmą ir generuoti galiojančius numerius, kurie praeina Luhn patikrinimą.

Kaip veikia Luhn algoritmas

Luhn algoritmas veikia taip:

1. Pradedant nuo dešiniojo skaitmens (neįskaitant kontrolinio skaitmens) ir judant į kairę, padvigubinkite kiekvieno antro skaitmens reikšmę.
2. Jei šio padvigubinimo rezultatas viršija 9, atimkite 9 iš rezultato.
3. Sudėkite visus skaitmenis gautame sekoje.
4. Jei bendras skaičius modulo 10 yra lygus 0 (jei bendras skaičius baigiasi nuliu), tuomet numeris yra galiojantis pagal Luhn formulę; priešingu atveju jis nėra galiojantis.

Štai vizualinė Luhn algoritmo atvaizdavimo schema:

Formulė

Luhn algoritmas gali būti išreikštas matematiškai taip:

Tegu $d_i$ yra $i$-asis skaitmuo, skaičiuojant nuo dešiniojo skaitmens (neįskaitant kontrolinio skaitmens) ir judant į kairę. Tada kontrolinis skaitmuo $d_0$ pasirenkamas taip, kad:

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

Kur $\bmod$ yra modulo operacija.

Naudojimo atvejai

Luhn algoritmas turi įvairių taikymo sričių skirtingose srityse:

1. Kreditinių kortelių patvirtinimas: Dauguma kreditinių kortelių numerių yra patvirtinami naudojant Luhn algoritmą.
2. Kanados socialinio draudimo numeriai: Luhn algoritmas naudojamas šių identifikavimo numerių galiojimui patvirtinti.
3. IMEI numeriai: Mobiliojo telefono IMEI numeriai apima kontrolinį skaitmenį, kurį patvirtina Luhn algoritmas.
4. Nacionaliniai teikėjų identifikavimo (NPI) numeriai: Naudojami JAV sveikatos priežiūros sistemoje, šie numeriai yra patvirtinami naudojant Luhn algoritmą.
5. ISBN: Kai kurie ISBN-10 numeriai naudoja Luhn algoritmo variantą patvirtinimui.

Alternatyvos

Nors Luhn algoritmas yra plačiai naudojamas, yra ir kitų kontrolinių sumų algoritmų skirtingiems tikslams:

1. Damm algoritmas: Kitas kontrolinio skaitmens algoritmas, kuris aptinka visus vieno skaitmens klaidas ir visas gretimas transpozicijas.
2. Verhoeff algoritmas: Sudėtingesnis kontrolinio skaitmens algoritmas, kuris aptinka visas vieno skaitmens klaidas ir daugumą transpozicijų.
3. ISBN-13 kontrolinis skaitmuo: Naudoja kitokį algoritmą nei ISBN-10, kuris remiasi Luhn algoritmu.

Istorija

Luhn algoritmą sukūrė Hans Peter Luhn, IBM kompiuterių mokslininkas, 1954 metais. Luhn buvo informacijos mokslo pionierius ir jam priskiriama daugybė inovacijų, įskaitant KWIC (Key Word In Context) indeksavimo sistemą.

Algoritmas iš pradžių buvo sukurtas apsaugoti nuo atsitiktinių klaidų, o ne nuo piktybinių atakų. Svarbu pažymėti, kad nors Luhn algoritmas gali aptikti daugelį įprastų klaidų, jis nėra saugi šifravimo forma ir neturėtų būti naudojamas duomenų saugumo tikslais.

Nepaisant savo amžiaus, Luhn algoritmas išlieka plačiai naudojamas dėl savo paprastumo ir efektyvumo, aptinkant įprastas rašymo klaidas.

Įgyvendinimo pavyzdžiai

Štai keletas kodo pavyzdžių, kaip įgyvendinti Luhn algoritmą įvairiose programavimo kalbose:

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

## Pavyzdžio naudojimas:
print(luhn_validate(4532015112830366))  # True
print(luhn_validate(4532015112830367))  # False
print(generate_valid_number(16))  # Generuoja galiojantį 16 skaitmenų numerį

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

// Pavyzdžio naudojimas:
console.log(luhnValidate(4532015112830366));  // true
console.log(luhnValidate(4532015112830367));  // false
console.log(generateValidNumber(16));  // Generuoja galiojantį 16 skaitmenų numerį

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));  // Generuoja galiojantį 16 skaitmenų numerį
    }
}

Kraštutiniai atvejai ir specialūs svarstymai

Įgyvendinant Luhn algoritmą, atsižvelkite į šiuos kraštutinius atvejus ir specialius svarstymus:

1. Įvesties patikrinimas: Užtikrinkite, kad įvestis būtų galiojantis numerio simbolių rinkinys. Ne skaitmeniniai simboliai turėtų būti tinkamai apdoroti (arba pašalinti, arba laikomi negaliojančia įvestimi).

2. Pirmieji nuliai: Algoritmas turėtų teisingai veikti su numeriais, turinčiais pirmuosius nulius.

3. Dideli numeriai: Būkite pasiruošę tvarkyti labai ilgus numerius, kurie gali viršyti standartinių sveikųjų skaičių tipų talpą kai kuriose programavimo kalbose.

4. Tuščia įvestis: Apibrėžkite, kaip jūsų įgyvendinimas turėtų tvarkyti tuščius simbolių rinkinius arba null įvestis.

5. Ne standartiniai simbolių rinkiniai: Kai kuriose programose galite susidurti su numeriais, kurie yra atvaizduojami simboliais už standartinio 0-9 intervalo. Apibrėžkite, kaip šie turėtų būti tvarkomi.

6. Veiklos svarstymai: Programoms, kurioms reikia greitai patvirtinti didelį skaičių įvesties, apsvarstykite algoritmo įgyvendinimo optimizavimą.

Skaitmeniniai pavyzdžiai

1. Galiojantis kreditinės kortelės numeris:

   • Numeris: 4532015112830366
   • Luhn patikrinimas: Galiojantis

2. Negaliojantis kreditinės kortelės numeris:

   • Numeris: 4532015112830367
   • Luhn patikrinimas: Negaliojantis

3. Galiojantis Kanados socialinio draudimo numeris:

   • Numeris: 046 454 286
   • Luhn patikrinimas: Galiojantis

4. Negaliojantis IMEI numeris:

   • Numeris: 490154203237518
   • Luhn patikrinimas: Negaliojantis

Testavimo atvejai

Norėdami patvirtinti Luhn algoritmo įgyvendinimą, galite naudoti šiuos testavimo atvejus:

def test_luhn_algorithm():
    assert luhn_validate(4532015112830366) == True
    assert luhn_validate(4532015112830367) == False
    assert luhn_validate(79927398713) == True
    assert luhn_validate(79927398714) == False
    
    # Testuokite generuotus numerius
    for _ in range(10):
        assert luhn_validate(generate_valid_number(16)) == True
    
    print("Visi testai praėjo!")

test_luhn_algorithm()

Nuorodos

1. Luhn, H. P. (1960). "Kompiuteris, patvirtinantis numerius". JAV patentas 2,950,048.
2. Gallian, Joseph. "Identifikavimo numerių matematika." Koleginė matematikos žurnalas, t. 22, nr. 3, 1991, p. 194–202. JSTOR, www.jstor.org/stable/2686878.
3. "ISO/IEC 7812-1:2017". Tarptautinė standartizacijos organizacija. Gauta 2024 m. rugpjūčio 2 d.
4. Knuth, Donald. "Kompiuterinės programavimo meno menas, 2 tomas: Seminumeriniai algoritmai". Addison-Wesley, 1997.