La formula di Luhn
Mercoledì, Febbraio 18th, 2009La formula di Luhn (detta anche algoritmo di Luhn o mod(10)) serve a verificare la validità di alcuni identificativi numerici, come i numeri delle carte di credito.
Il procedimento è il seguente:
- Partiamo dall’ultima cifra, che per noi sarà la prima, e ci spostiamo verso sinistra. Moltiplichiamo per 2 tutte le cifre che si trovano in posizioni pari (2, 4, 6 etc). Se il risultato è composto da due cifre, le addizioniamo tra loro, ottenendo così un risultato composto da una cifra sola (14 diventa: 1+4=5)
- Sommiamo tra loro tutte le cifre, sia che si trovino in posizione pari, sia che siano in posizione dispari.
- Se il risultato ottenuto è divisibile per 10 (il risultato è un numero intero e non c’è resto), il numero è valido.
Si noti che questa formula non verifica di quanti numeri è composto il numero. Per controllare che sia un numero di carta di credito bisognerebbe almeno controllare che sia composto da 16 cifre. Inoltre la formula di Luhn non effettua alcun controllo riguardo la data di scadenza della carta nè altri dati importanti.
Deve essere quindi considerata come una formula generica atta a verificare che non ci siano stati errori di digitazione, nient’altro.
Ora vediamo le implementazioni in linguaggio PHP e in Gambas.
Formula di Luhn in Gambas
PUBLIC FUNCTION Luhn(StrInput AS String) AS Boolean
DIM i AS Integer ' digit index
DIM CurrentDigit AS Integer ' current digit being processed
DIM isEven AS Boolean ' if true, the digit must be processed
DIM IntTotal AS Integer ' total for the last computation
isEven = FALSE
i = Len(StrInput) - 1
WHILE i >= 0
CurrentDigit = CInt(CharAt(StrInput, i))
IF isEven THEN
CurrentDigit *= 2
IF CurrentDigit > 9 THEN
CurrentDigit -= 9
ENDIF
ENDIF
IntTotal += CurrentDigit
isEven = NOT isEven
i -= 1
WEND
IF (IntTotal MOD 10) = 0 THEN
RETURN TRUE
ELSE
RETURN FALSE
ENDIF
END
PUBLIC FUNCTION IsCreditCard(StrInput AS String) AS Boolean
IF Len(StrInput) <> 16 THEN
RETURN FALSE
ENDIF
RETURN Luhn(StrInput)
END
Formula di Luhn in PHP
function mod_10($code)
{
setType($code, 'string');
$isEven = false;
$total = 0;
for ($i=strlen($code)-1; $i>=0; $i--) {
$digit = substr($code, $i, 1);
if ($isEven) {
$digit *= 2;
if ($digit>9)
$digit -= 9;
}
$total += $digit;
$isEven = !$isEven;
}
return (bool) !($total % 10);
}
function is_credit_card($code)
{
return (strlen($code)==16) && mod_10($code);
}
Note
Il procedimento è lo stesso in entrambi i linguaggi.
Per motivi di performance, ho scritto un unico ciclo nel quale viene eseguita la moltiplicazione per due quando è il caso, per poi sommare il risultato (o il numero non moltiplicato) al totale.
Ho semplificato anche la somma delle due cifre che compongono il risultato della moltiplicazione. Ho potuto farlo perchè so che la cifra di sinistra è sempre 1. Se la togliessimo bisognerebbe sottrarre 10. Siccome dopo bisognerebbe aggiungere 1, è meglio fin dall’inizio sottrarre 9 al numero a due cifre.
Per controllare se un risultato è divisibile per 10 si utilizza l’operatore modulus (’MOD’ in Gambas e ‘%’ in PHP), che restituisce il resto di una divisione.
Generare numeri validi
Abbiamo visto che, perchè un numero sia valido, è sufficiente che il procedimento sopra spiegato generi un totale divisibile per 10. Si può quindi generare un ID valido (UNO: mai 0, mai 2), di n cifre, partendo da una qualsiasi combinazione di cifre lunga n-1.
Il procedimento per ottenerlo è molto semplice: aggiungiamo uno 0 a destra e applichiamo all’id la formula di Luhn. Se il risultato è divisibile per 10 abbiamo già ottenuto ciò che vogliamo. Altrimenti occorre sostituire lo 0 con la cifra corretta. Prendiamo la cifra più a destra del risultato ottenuto (per 64 è 4); la chiameremo d. Eseguiamo 10 - d. Il risultato è la cifra che dovrà sostituire lo 0 che abbiamo inserito.
Essendo la formula molto semplice, non è il caso di riscriverla in entrambi i linguaggi.
Generare id di Luhn validi in PHP
function luhn_generate($code)
{
setType($code, 'string');
$code .= '0';
$isEven = false;
$total = 0;
for ($i=strlen($code)-1; $i>=0; $i--) {
$digit = substr($code, $i, 1);
if ($isEven) {
$digit *= 2;
if ($digit>9)
$digit -= 9;
}
$total += $digit;
$isEven = !$isEven;
}
if ($total % 10) {
$digit = $total % 10;
$digit = 10 - $digit;
$code = substr($code, 0, strlen($code)-1) . $digit;
}
return $code;
}
Si potrebbero apportare un paio di ottimizzazioni ma, siccome non sono fondamentali e renderebbero il codice un po’ meno chiaro, lascio al lettore volenteroso il compito di trovarle. Il chè mi porta a dare un consiglio generale: se volete aggiungere modifiche che riducono la leggibilità documentate il tutto (come io non ho fatto in questi esempi) e apportatele solo dopo aver scritto un codice un po’ meno ottimizzato ma ben funzionante.
Dimostrazione
Vedi il mio demo per la verifica e la generazione di id validi. Utilizza le funzioni PHP esposte in questa pagina:
Buon divertimento e restate liberi.