Calculator pentru Algoritmul Luhn

Calculator pentru Algoritmul Luhn

Introducere

Algoritmul Luhn, cunoscut și sub numele de algoritmul "modulus 10" sau "mod 10", este o formulă simplă de verificare utilizată pentru a valida o varietate de numere de identificare, cum ar fi numerele de carduri de credit, numerele de asigurare socială canadiene, numerele IMEI și numerele de identificare a furnizorilor naționali în Statele Unite. Acest calculator vă permite să validați numere folosind algoritmul Luhn și să generați numere valide care trec verificarea Luhn.

Cum funcționează algoritmul Luhn

Algoritmul Luhn funcționează astfel:

1. Începând de la cifra din dreapta (excluzând cifra de verificare) și mergând spre stânga, dublați valoarea fiecărei a doua cifre.
2. Dacă rezultatul acestei operații de dublare este mai mare decât 9, scădeți 9 din rezultat.
3. Adunați toate cifrele din secvența rezultată.
4. Dacă totalul modulo 10 este egal cu 0 (dacă totalul se termină cu zero), atunci numărul este valid conform formulei Luhn; altfel, nu este valid.

Iată o reprezentare vizuală a algoritmului Luhn:

Formula

Algoritmul Luhn poate fi exprimat matematic astfel:

Fie $d_i$ cifra $i$-a, numărând de la cifra din dreapta (excluzând cifra de verificare) și mergând spre stânga. Atunci cifra de verificare $d_0$ este aleasă astfel încât:

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

Unde $\bmod$ este operația modulo.

Cazuri de utilizare

Algoritmul Luhn are diverse aplicații în diferite domenii:

1. Validarea cardurilor de credit: Cele mai multe numere de carduri de credit sunt validate folosind algoritmul Luhn.
2. Numerele de asigurare socială canadiene: Algoritmul Luhn este utilizat pentru a verifica validitatea acestor numere de identificare.
3. Numerele IMEI: Numerele IMEI ale telefoanelor mobile includ o cifră de verificare validată de algoritmul Luhn.
4. Numerele de identificare a furnizorilor naționali (NPI): Folosite în sistemul de sănătate din Statele Unite, aceste numere sunt validate folosind algoritmul Luhn.
5. ISBN-uri: Unele numere ISBN-10 folosesc o variantă a algoritmului Luhn pentru validare.

Alternative

Deși algoritmul Luhn este utilizat pe scară largă, există și alte algoritmi de verificare pentru diferite scopuri:

1. Algoritmul Damm: Un alt algoritm de cifră de verificare care detectează toate erorile de un singur digit și toate erorile de transpoziție adiacente.
2. Algoritmul Verhoeff: Un algoritm de verificare mai complex care prinde toate erorile de un singur digit și cele mai multe erori de transpoziție.
3. Cifra de verificare ISBN-13: Folosește un algoritm diferit față de ISBN-10, care se bazează pe algoritmul Luhn.

Istorie

Algoritmul Luhn a fost creat de Hans Peter Luhn, un om de știință informatician de la IBM, în 1954. Luhn a fost un pionier în domeniul științei informației și este creditat cu mai multe inovații, inclusiv sistemul de indexare KWIC (Cuvânt cheie în context).

Algoritmul a fost inițial conceput pentru a proteja împotriva erorilor accidentale, nu a atacurilor malițioase. Este important de menționat că, deși algoritmul Luhn poate detecta multe erori comune, nu este o formă sigură de criptare și nu ar trebui să fie utilizat pentru scopuri de securitate a datelor.

În ciuda vârstei sale, algoritmul Luhn rămâne utilizat pe scară largă datorită simplității și eficienței sale în prinderea erorilor comune de transcriere.

Exemple de implementare

Iată câteva exemple de cod pentru a implementa algoritmul Luhn în diferite limbaje de programare:

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

## Exemplu de utilizare:
print(luhn_validate(4532015112830366))  # True
print(luhn_validate(4532015112830367))  # False
print(generate_valid_number(16))  # Generează un număr valid de 16 cifre

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

// Exemplu de utilizare:
console.log(luhnValidate(4532015112830366));  // true
console.log(luhnValidate(4532015112830367));  // false
console.log(generateValidNumber(16));  // Generează un număr valid de 16 cifre

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));  // Generează un număr valid de 16 cifre
    }
}

Cazuri limită și considerații speciale

Când implementați algoritmul Luhn, luați în considerare următoarele cazuri limită și considerații speciale:

1. Validarea intrării: Asigurați-vă că intrarea este un șir de numere valid. Caracteristicile non-digit ar trebui să fie gestionate corespunzător (fie eliminate, fie tratate ca intrări invalide).

2. Zeros la început: Algoritmul ar trebui să funcționeze corect cu numere care au zerouri la început.

3. Numere mari: Fiți pregătit să gestionați numere foarte lungi care ar putea depăși capacitatea tipurilor standard de integer în unele limbaje de programare.

4. Intrare goală: Definiți cum ar trebui să gestioneze implementarea dvs. șirurile goale sau intrările nule.

5. Seturi de caractere non-standard: În unele aplicații, s-ar putea să întâlniți numere reprezentate cu caractere în afara intervalului standard 0-9. Definiți cum ar trebui să fie gestionate acestea.

6. Considerații de performanță: Pentru aplicațiile care trebuie să valideze rapid un număr mare de intrări, luați în considerare optimizarea implementării algoritmului.

Exemple numerice

1. Număr valid de card de credit:

   • Număr: 4532015112830366
   • Verificare Luhn: Valabil

2. Număr invalid de card de credit:

   • Număr: 4532015112830367
   • Verificare Luhn: Invalid

3. Număr valid de asigurare socială canadiană:

   • Număr: 046 454 286
   • Verificare Luhn: Valabil

4. Număr IMEI invalid:

   • Număr: 490154203237518
   • Verificare Luhn: Invalid

Cazuri de testare

Pentru a verifica implementarea algoritmului Luhn, puteți folosi următoarele cazuri de testare:

def test_luhn_algorithm():
    assert luhn_validate(4532015112830366) == True
    assert luhn_validate(4532015112830367) == False
    assert luhn_validate(79927398713) == True
    assert luhn_validate(79927398714) == False
    
    # Testați numerele generate
    for _ in range(10):
        assert luhn_validate(generate_valid_number(16)) == True
    
    print("Toate testele au trecut!")

test_luhn_algorithm()

Referințe

1. Luhn, H. P. (1960). "Computer for Verifying Numbers". Patentul SUA 2,950,048.
2. Gallian, Joseph. "Matematica numerelor de identificare." Jurnalul de matematică a colegiului, vol. 22, nr. 3, 1991, pp. 194–202. JSTOR, www.jstor.org/stable/2686878.
3. "ISO/IEC 7812-1:2017". Organizația Internațională de Standardizare. Accesat pe 2 august 2024.
4. Knuth, Donald. "Arta programării computerizate, Volumul 2: Algoritmi seminumerici". Addison-Wesley, 1997.