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.

Descrizione dell'algoritmo per il calcolo della cifra di Luhn

La cifra di controllo di tipo Luhn viene calcolata in modo semplice. Si sommano tutte le cifre in posizione pari al doppio della somma di quelle in posizione dispari. Si considera quindi 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 modulo è 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 modulo. Ad esempio se la somma = 61 che diviso per 10 dà resto 1, la cifra di Luhn sarà 9 (10-1)

Verifica del numero

Il controllo di un numero contenente la cifra di Luhn si basa su tre passi:

1. Partendo da destra e spostandosi verso sinistra, moltiplicare per 2 ogni cifra posta in posizione pari
2. Laddove la moltiplicazione ha 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

La formula di Luhn viene utilizzata in Canada dal Social Insurance Number per l'identificazione dei suoi clienti; tuttavia con la seguente formula non verifica ulteriori informazioni, come il numero delle cifre e la validità della data di scadenza. Del resto la formula è stata studiata per rilevare errori di digitazione, non è adatta a rilevare falsificazioni volontarie.

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.

/**
* 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 = 0; i < stringaNumerica.length(); i++)
    {
        int cifraCorrente = atoi(stringaNumerica.substr(stringaNumerica.length()- i, 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
}

Algoritmo per la verifica in R

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

Algoritmo in VBA per Excel 2007

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

Collegamenti esterni

• 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