# Formula di Luhn

La formula di Luhn, anche conosciuta come Modulo 10, è un semplice algoritmo che consente di generare e verificare la validità di vari numeri identificativi. Venne ideata nel 1954 dall'informatico dell'IBM Hans Peter Luhn e brevettata nel 1960. Ora di pubblico dominio ha molteplici applicazioni, ad esempio per i numeri delle carte di credito. Ogni carta di credito ha un suo numero di carta (es. 0000-1234-5678-9123) dove la prima parte identifica il circuito internazionale (Visa, American Express, Mastercard...) mentre il resto la banca emittente ed il cliente. L'ultima è la cifra di controllo. La formula di Luhn viene utilizzata in molti codici numerici, ad esempio in Canada dal Social Insurance Number e in Italia nella partita IVA.
Lo scopo del procedimento è quello di rilevare errori involontari di trascrizione e digitazione, e non è certo adatta a rilevare falsificazioni volontarie.

## Descrizione dell'algoritmo per il calcolo della cifra di Luhn

Esistono modi diversi per ottenere la cifra di controllo. Nel già citato brevetto 2950048 del 1960, Luhn descrive la procedura dicendo che si sommano le cifre rimpiazzandone una sì e una no con cifre "sostitute". Se il numero identificativo originale ha un numero dispari di cifre si comincia rimpiazzando la prima cifra, poi la seconda no, poi la terza sì, e così via. Se invece il numero identificativo originale ha un numero pari di cifre, la prima cifra viene lasciata così com'è e si rimpiazza la seconda cifra, poi la terza no, e così via. Le cifre sostitute si ottengono da quelle originali, moltiplicandole per due e sommando assieme le decine e le unità. Questa è la tabella con le sostituzioni:
| Cifra originale | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| Cifra sostituta | 0 | 2 | 4 | 6 | 8 | 1 | 3 | 5 | 7 | 9 |
Una volta effettuate queste sostituzioni, si sommano le cifre tenendo ad ogni somma solo le unità. Questo è equivalente a sommare tutte le cifre e considerare poi il modulo rispetto a 10 (ovvero il resto della divisione per 10) del valore così ottenuto; si determina quindi la cifra di Luhn come segue:
* se il risultato è 0 (la somma è divisibile per 10) la cifra di controllo sarà 0. Ad esempio se la somma = 60 che diviso per 10 dà resto 0, la cifra di Luhn sarà 0
* altrimenti la cifra di Luhn sarà la differenza tra 10 ed il risultato. Ad esempio se la somma = 61 che diviso per 10 dà resto 1, la cifra di Luhn sarà 9 (10-1)
Consideriamo ad esempio il numero identificativo 4872148. Volendo aggiungere una cifra di controllo con l'algoritmo descritto si nota che è composto di 7 cifre e quindi dobbiamo sostituire le cifre a partire dalla prima: 4→8, 8, 7→5, 2, 1→2, 4, 8→7. Quindi 4872148→8852247. Sommiamo le cifre e otteniamo 8+8=16→6, 6+5=11→1, 1+2=3, 3+2=5, 5+4=9, 9+7=16→6. (In modo equivalente potevamo calcolare 8+8+5+2+2+4+7=36→6). La cifra di controllo è quindi 10-6=4. La cifra viene aggiunta a destra del numero identificativo, che diventa quindi 48721484.
Facciamo ora un esempio con un numero di cifre pari: 123456. Dobbiamo sostituire le cifre a partire dalla seconda: 1, 2→4, 3, 4→8, 5, 6→3. Quindi 123456→143853. Sommiamo le cifre e otteniamo 1+4=5, 5+3=8, 8+8=16→6, 6+5=11→1, 1+3=4. (In modo equivalente potevamo calcolare 1+4+3+8+5+3=24→4). La cifra di controllo è quindi 10-4=6. La cifra viene aggiunta a destra del numero identificativo, che diventa quindi 1234566.

## Verifica del numero

Per verificare se un numero con cifra di controllo è corretto, si può procedere calcolando la cifra di controllo come descritto sopra, ignorando la cifra di controllo e poi verificare se questa corrisponde. Alternativamente si può anche procedere utilizzando nell'algoritmo anche la cifra stessa e verificando che il risultato sia 0. Una descrizione alternativa della verifica includendo anche la cifra di controllo può essere questa:
* Partendo da destra e spostandosi verso sinistra, moltiplicare per 2 ogni cifra posta in posizione pari (ovvero l'ultima no, dato che è la cifra di controllo, la penultima sì, la terzultima no, e così via);
* Laddove la moltiplicazione abbia dato un risultato a due cifre, sommare le due cifre per ottenerne una sola (es. 18 = 1+8)
* Sommare tutte le cifre, sia quelle che si trovano in posizione pari, sia quelle che si trovano in posizione dispari
Se la somma complessiva è divisibile per 10 (la divisione non ha resto) la carta è valida.
Ad esempio, supponendo di avere il seguente numero di carta: 4716-4359-1733-0099 (quindi 9900367291386278)
* 9+9+0+0+3+6+7+2+9+1+3+8+6+2+7+8=80
* 80/10 = 8 = risultato intero → carta valida
Lo stesso numero può essere verificato generando la cifra di controllo e verificando che sia 9. Il numero di cifre è dispari quindi sostituiamo a partire dalla prima: 4→8, 7, 1→2, 6, 4→8, 3, 5→1, 9, 1→2, 7, 3→6, 3, 0→0, 0, 9→9. Quindi 471643591733009→872683192763009. Sommiamo le cifre e otteniamo 8+7=15→5, 5+2=7, 7+6=13→3, 3+8=11→1, 1+3=4, 4+1=5, 5+9=14→4, 4+2=6, 6+7=13→3, 3+6=9, 9+3=12→2, 2+0=2, 2+0=2, 2+9=11→1. (In modo equivalente potevamo calcolare 8+7+2+6+8+3+1+9+2+7+6+3+0+0+9=71→1). La cifra di controllo è quindi 10-1=9. E come sopra il codice risulta corretto.

## Algoritmo in C++

La funzione qui presentata, in C++ non ha come scopo quello di essere ottimizzata quanto quello di essere chiara. Oltre ad eventuali ottimizzazioni una funzione più completa potrebbe, ad esempio, verificare che la stringa passata in input contenga davvero esclusivamente cifre decimali. I commenti ed i nomi delle variabili il più possibile autodescriventi dovrebbero rendere chiaro il funzionamento dell'algoritmo.