Algoritm Luhn - Luhn algorithm

Luhn algoritm sau formula Luhn , de asemenea , cunoscut sub numele de „ modulul 10“ sau „mod de 10“ algoritm , numit după creatorul său, IBM om de știință Hans Peter Luhn , este o simplă sumă de control formulă utilizată pentru a valida o varietate de numere de identificare, cum ar fi de credit numere de cărți , numere IMEI , numere de identificare național furnizorului în statele Unite, Canada numere de asigurare socială , israeliene numere de identificare, Africa de Sud numere de identificare, suedeză numere de identificare la nivel național , suedeză numere de identitate (OrgNr), greacă numerele de securitate socială (ΑΜΚΑ), Numerele cartelei SIM și codurile de sondaj care apar pe chitanțele McDonald's , Taco Bell și Tractor Supply Co. Este descris în brevetul SUA nr. 2.950.048, acordat la 23 august 1960.

Algoritmul este în domeniul public și este utilizat în prezent pe scară largă. Este specificat în ISO / IEC 7812 -1. Nu este destinat să fie o funcție hash securizată criptografic ; a fost conceput pentru a proteja împotriva erorilor accidentale, nu a atacurilor rău intenționate. Majoritatea cardurilor de credit și numeroase numere de identificare guvernamentale folosesc algoritmul ca o metodă simplă de a distinge numerele valide de numerele greșite sau altfel incorecte.

Descriere

Cifra de verificare este calculată după cum urmează:

1. Luați numărul original și începând de la cifra din dreapta, deplasându-vă la stânga, dublați valoarea fiecărei a doua cifre (inclusiv cea din dreapta).
2. Înlocuiți valoarea rezultată la fiecare poziție cu suma cifrelor valorii acestei poziții.
3. Însumați valorile rezultate din toate pozițiile ( s ).
4. Cifra de verificare calculată este egală cu .${\ displaystyle 10-s \ operatorname {mod} 10}$

Exemplu pentru calcularea cifrei de verificare

Să presupunem un exemplu de număr de cont „7992739871” (doar „sarcina utilă”, cifra de verificare nu este încă inclusă):

Suma cifrelor rezultate este 67.

Cifra de verificare este egală cu . ${\ displaystyle 10-67 \ operatorname {mod} 10 = 3}$

Acest lucru face ca numărul contului complet să fie citit 79927398713.

Exemplu pentru validarea cifrei de verificare

Trebuie doar să tăiați cifra de verificare (ultima cifră) a numărului pentru validare. 79927398713 -> 7992739871 Calculați cifra de verificare (vezi mai sus) (3) și comparați rezultatul cu cifra de verificare pe care ați tăiat-o (3 = 3). Dacă se potrivesc cu numărul trecut testul.

Punctele forte și punctele slabe

Algoritmul Luhn va detecta orice eroare dintr-o singură cifră, precum și aproape toate transpunerile de cifre adiacente. Cu toate acestea, nu va detecta transpunerea secvenței din două cifre 09 la 90 (sau invers). Acesta va detecta majoritatea posibilelor erori gemene (nu va detecta 22 ↔ 55 , 33 ↔ 66 sau 44 ↔ 77 ).

Alți algoritmi mai complexi cu cifre de verificare (cum ar fi algoritmul Verhoeff și algoritmul Damm ) pot detecta mai multe erori de transcriere. Luhn mod N Algoritmul este o extensie care suportă șiruri non-numerice.

Deoarece algoritmul funcționează pe cifre de la dreapta la stânga și zero cifre afectează rezultatul numai dacă provoacă schimbarea poziției, completarea zero a începutului unui șir de numere nu afectează calculul. Prin urmare, sistemele care se tamponează la un anumit număr de cifre (de exemplu, convertind 1234 la 0001234) pot efectua validarea Luhn înainte sau după umplere și pot obține același rezultat.

Algoritmul a apărut într-un brevet al Statelor Unite pentru un dispozitiv mecanic de mână pentru calculul sumei de control. Prin urmare, se cerea să fie destul de simplu. Dispozitivul a luat suma mod 10 prin mijloace mecanice. Cifrele de substituție , adică rezultatele procedurii duble și reduse, nu au fost produse mecanic. Mai degrabă, cifrele au fost marcate în ordinea lor permutată pe corpul mașinii.

Implementarea pseudocodului

function checkLuhn(string purportedCC) {
    int nDigits := length(purportedCC)
    int sum := integer(purportedCC[nDigits-1])
    int parity := (nDigits-1) modulus 2
    for i from 0 to nDigits - 2 {
        int digit := integer(purportedCC[i])
        if i modulus 2 = parity
            digit := digit × 2
        if digit > 9
            digit := digit - 9 
        sum := sum + digit
    }
    return (sum modulus 10) = 0
}

Referințe

linkuri externe

• Implementare în 88 de limbi pentru proiectul Cod Rosetta