Calcolatore dell'Algoritmo di Luhn

Introduzione

L'algoritmo di Luhn, noto anche come algoritmo "modulus 10" o "mod 10", è una semplice formula di checksum utilizzata per convalidare una varietà di numeri identificativi, come numeri di carte di credito, numeri di previdenza sociale canadesi, numeri IMEI e numeri di identificazione del fornitore nazionale negli Stati Uniti. Questo calcolatore ti consente di convalidare numeri utilizzando l'algoritmo di Luhn e generare numeri validi che superano il controllo di Luhn.

Come Funziona l'Algoritmo di Luhn

L'algoritmo di Luhn funziona come segue:

Partendo dalla cifra più a destra (escludendo la cifra di controllo) e muovendosi verso sinistra, raddoppia il valore di ogni secondo numero.
Se il risultato di questa operazione di raddoppio è maggiore di 9, sottrai 9 dal risultato.
Somma tutte le cifre nella sequenza risultante.
Se il totale modulo 10 è uguale a 0 (se il totale termina in zero), allora il numero è valido secondo la formula di Luhn; altrimenti, non è valido.

Ecco una rappresentazione visiva dell'algoritmo di Luhn:

Formula

L'algoritmo di Luhn può essere espresso matematicamente come segue:

Sia $d_i$ la $i$ -esima cifra, contando dalla cifra più a destra (escludendo la cifra di controllo) e muovendosi verso sinistra. Quindi la cifra di controllo $d_0$ è scelta in modo che:

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

Dove $\bmod$ è l'operazione modulo.

Casi d'Uso

L'algoritmo di Luhn ha varie applicazioni in diversi campi:

Validazione delle Carte di Credito: La maggior parte dei numeri di carte di credito è convalidata utilizzando l'algoritmo di Luhn.
Numeri di Previdenza Sociale Canadesi: L'algoritmo di Luhn è utilizzato per verificare la validità di questi numeri identificativi.
Numeri IMEI: I numeri IMEI dei telefoni cellulari incorporano una cifra di controllo convalidata dall'algoritmo di Luhn.
Numeri di Identificazione del Fornitore Nazionale (NPI): Utilizzati nel sistema sanitario degli Stati Uniti, questi numeri sono convalidati utilizzando l'algoritmo di Luhn.
ISBN: Alcuni numeri ISBN-10 utilizzano una variante dell'algoritmo di Luhn per la validazione.

Alternative

Sebbene l'algoritmo di Luhn sia ampiamente utilizzato, ci sono altri algoritmi di checksum per scopi diversi:

Algoritmo di Damm: Un altro algoritmo di cifra di controllo che rileva tutti gli errori a cifra singola e tutti gli errori di trasposizione adiacenti.
Algoritmo di Verhoeff: Un algoritmo di checksum più complesso che cattura tutti gli errori a cifra singola e la maggior parte degli errori di trasposizione.
Cifra di controllo ISBN-13: Utilizza un algoritmo diverso rispetto all'ISBN-10, che si basa sull'algoritmo di Luhn.

Storia

L'algoritmo di Luhn è stato creato da Hans Peter Luhn, un informatico dell'IBM, nel 1954. Luhn è stato un pioniere nel campo della scienza dell'informazione ed è accreditato con diverse innovazioni, incluso il sistema di indicizzazione KWIC (Key Word In Context).

L'algoritmo è stato originariamente progettato per proteggere contro errori accidentali, non attacchi malevoli. È importante notare che, sebbene l'algoritmo di Luhn possa rilevare molti errori comuni, non è una forma sicura di crittografia e non dovrebbe essere utilizzato per scopi di sicurezza dei dati.

Nonostante la sua età, l'algoritmo di Luhn rimane ampiamente utilizzato grazie alla sua semplicità ed efficacia nel rilevare errori comuni di trascrizione.

Esempi di Implementazione

Ecco alcuni esempi di codice per implementare l'algoritmo di Luhn in vari linguaggi di programmazione:

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

## Esempio di utilizzo:
print(luhn_validate(4532015112830366))  # True
print(luhn_validate(4532015112830367))  # False
print(generate_valid_number(16))  # Genera un numero valido di 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);
}

// Esempio di utilizzo:
console.log(luhnValidate(4532015112830366));  // true
console.log(luhnValidate(4532015112830367));  // false
console.log(generateValidNumber(16));  // Genera un numero valido di 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));  // Genera un numero valido di 16 cifre
    }
}

Casi Limite e Considerazioni Speciali

Quando si implementa l'algoritmo di Luhn, considera i seguenti casi limite e considerazioni speciali:

Validazione dell'Input: Assicurati che l'input sia una stringa numerica valida. I caratteri non numerici devono essere gestiti in modo appropriato (o rimossi o trattati come input non valido).
Zeri Iniziali: L'algoritmo dovrebbe funzionare correttamente con numeri che hanno zeri iniziali.
Numeri Grandi: Essere pronti a gestire numeri molto lunghi che potrebbero superare la capacità dei tipi interi standard in alcuni linguaggi di programmazione.
Input Vuoto: Definisci come la tua implementazione dovrebbe gestire stringhe vuote o input nulli.
Insiemi di Caratteri Non Standard: In alcune applicazioni, potresti incontrare numeri rappresentati con caratteri al di fuori dell'intervallo standard 0-9. Definisci come questi dovrebbero essere gestiti.
Considerazioni sulle Prestazioni: Per applicazioni che devono convalidare un gran numero di input rapidamente, considera di ottimizzare l'implementazione dell'algoritmo.

Esempi Numerici

Numero di Carta di Credito Valido:
- Numero: 4532015112830366
- Controllo Luhn: Valido
Numero di Carta di Credito Non Valido:
- Numero: 4532015112830367
- Controllo Luhn: Non Valido
Numero di Previdenza Sociale Canadese Valido:
- Numero: 046 454 286
- Controllo Luhn: Valido
Numero IMEI Non Valido:
- Numero: 490154203237518
- Controllo Luhn: Non Valido

Casi di Test

Per verificare l'implementazione dell'algoritmo di Luhn, puoi utilizzare i seguenti casi di test:

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 numeri generati
    for _ in range(10):
        assert luhn_validate(generate_valid_number(16)) == True
    
    print("Tutti i test sono stati superati!")

test_luhn_algorithm()

Riferimenti

Luhn, H. P. (1960). "Computer for Verifying Numbers". US Patent 2,950,048.
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.
"ISO/IEC 7812-1:2017". International Organization for Standardization. Retrieved August 2, 2024.
Knuth, Donald. "The Art of Computer Programming, Volume 2: Seminumerical Algorithms". Addison-Wesley, 1997.