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.^[1] 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.

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:

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.

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:

1. 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);
2. Laddove la moltiplicazione abbia dato un risultato a due cifre, sommare le due cifre per ottenerne una sola (es. 18 = 1+8)
3. 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)

1. 9+9+0+0+3+6+7+2+9+1+3+8+6+2+7+8=80
2. 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.

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.

/**
* La seguente funzione C++ calcola e restituisce la cifra di controllo secondo la formula di Luhn.
* Prende come parametro una stringa numerica decimale, ovviamente senza la cifra di controllo.
*/
int calcolaCifraDiControlloLuhn(string stringaNumerica)
{
    int somma = 0;
    
    if (stringaNumerica.length() % 2 != 0)
	    stringaNumerica = "0" + stringaNumerica;  // aggiunge uno 0 se il numero di cifre è dispari
    
    for(int i = 1; i <= stringaNumerica.length(); i++)
    {
        int cifraCorrente = atoi(stringaNumerica.substr(i - 1, 1).c_str());  // converti il carattere corrente in int
        int daSommare;
        
        if ((i % 2) == 0)  // le cifre in posizione pari vengono raddoppiate
        {
            int cifraRaddoppiata = cifraCorrente * 2;
            if(cifraRaddoppiata >= 10)
                daSommare = 1 + (cifraRaddoppiata % 10);  // somma le cifre se il numero è > 10
            else
                daSommare = cifraRaddoppiata;
        }
        else  // le cifre in posizione dispari sono sommate così come sono
            daSommare = cifraCorrente;

        somma += daSommare;  // aggiornamento del risultato parziale
    }
    
    if (somma % 10 == 0)  // se la somma è divisibile per 10, restituisci 0
        return 0;
    else
        return 10 - (somma % 10);  // altrimenti, restituisci 10 - il modulo 10 della somma
}

# La seguente funzione R verifica se il numero in input è valido o meno secondo il criterio di Luhn.
# Prende come parametro "x" costituito da una stringa numerica 
# resituisce in output TRUE o FALSE a seconda che il numero sia valido (TRUE) o no (FALSE). 

verificaNumeroLuhn <- function(x, quiet = FALSE){
  
  # Controllo: solo character 
  if(!inherits(x, "character")) {
    stop('x must be a character.')
  }
  
  # trasformazione in vettore numerico
  y <- strsplit(x, "")[[1]]
  y <- as.integer(y)
  
  # inversione dell'ordine 
  y_reverse <- y[c(seq(length(y),1,-1))]
  
  # ciclo per il controllo
  for(i in 1:length(y_reverse)) {
    
    # SE indice pari
    if(i %% 2 == 0){

      y_reverse[i] <- 2*y_reverse[i]
    
      # se somma maggiore di 10
      if(y_reverse[i] >= 10){

        y_split <- as.character(y_reverse[i])
        y_split <- strsplit(y_split, "")[[1]]
        y_split <- as.integer(y_split)
        y_reverse[i] <- sum(y_split)

      }
    } else {
      # SE indice dispari
      next
    }
  }

  # Controllo Validita
  if(sum(y_reverse) %% 10 == 0){
    if(!quiet) message("Numero Valido")
    return(TRUE)
  } else {
    if(!quiet) message("Numero NON Valido")
    return(FALSE)
  }
}

Function LUHN(stringaNumerica As String) As Integer

    'La presente funzione calcola e restituisce la cifra di controllo secondo la formula di Luhn

    'ricevendo in ingresso una stringa numerica decimale, priva del numero di controllo.

    Dim somma As Integer , cifraCorrente As Integer , daSommare As Integer, cifraRaddoppiata As Integer
    somma = 0
    If ((Len(stringaNumerica) Mod 2) <> 0) Then
        stringaNumerica = "0" + stringaNumerica
    End If
    For i = 1 To Len(stringaNumerica)
        cifraCorrente = CInt(Mid(stringaNumerica, Len(stringaNumerica) + 1 - i, 1))
        If (i Mod 2) <> 0 Then                
            cifraRaddoppiata = cifraCorrente * 2
            If cifraRaddoppiata >= 10 Then
                daSommare = 1 + (cifraRaddoppiata Mod 10)  'somma le cifre se il numero è > 10
            Else
                daSommare = cifraRaddoppiata
            End If
        Else  
            daSommare = cifraCorrente
        End If
        somma = somma + daSommare  
      Next
    If (somma Mod 10) = 0 Then   
        LUHN = 0
    Else
        LUHN = 10 - (somma Mod 10) 
    End If
End Function

Portale Matematica: accedi alle voci di Teknopedia che trattano di matematica

• Implementazione algoritmo di Luhn in R (Implementazione dell'algoritmo di Luhn e della scomposizione e verifica della validità di una partita Iva italiana.)

• Implementazione controllo per la cifra di Luhn