Algorytm Luhna

Algorytm Luhna (autor: Hans Peter Luhn - naukowiec z IBM) jest najczęściej wykorzystywanym sposobem sprawdzenia poprawności ciągu liczb. Jego zastosowanie to sprawdzanie numerów kart kredytowych i innych np. lojalnościowych, numerów IMEI, numerów ubezpieczeń itd. Algorytm działa na pojedynczych cyfrach od prawej do lewej strony sprawdzanej liczby. Sam schemat jest bardzo prosty i sprowadza się do kilku kroków:

1. sumujemy cyfry nieparzyste (pierwszą, trzecią, piąta itd.),
2. podwajamy cyfry parzyste (drugą, czwartą, szóstą itd.), jeśli podwojona wartość jest większa od 9, sumujemy cyfry (np. podwajamy 8, dostajemy 16, wartość większa od 9, sumujemy cyfry 1+6, dostajemy wynik 7),
3. sumujemy otrzymane cyfry z kroku drugiego,
4. dodajemy dwie sumy (dla cyfr parzystych i nieparzystych), jeśli wynik modulo 10 daje 0 to liczba jest poprawna, w przeciwnym przypadku niepoprawna.

Przeanalizujmy algorytm na prostym przykladzie. Mamy numer karty: 4853928344613904. Poruszamy się od prawej do lewej strony. Obliczamy sumę cyfr nieparzystych:

sumaNieparzystych = 4 + 9 + 1 + 4 + 3 + 2 + 3 + 8 = 34

Obliczamy sumę podwojonych cyfr parzystych (jeśli podwojona wartość jest większa od 9 dodajemy poszczególne cyfry):

sumaParzystych = 0 + 6 + (1+2) + 8 + (1+6) + (1+8) + (1+0) + 8 = 42

Dodajemy otrzymane wyniki:

sumaParzystych + sumaNieparzystych = 76

Reszta z dzielenia 76 przez 10 (76 modulo 10) nie jest zerem więc nasz numer nie jest poprawny.

Zapiszmy algorytm wykorzystując Javę. Metoda czyPoprawna() zwróci nam wartość logiczną świadczącą o poprawności bądź też nie sprawdzanego ciągu cyfr.

/**
 * Implementacja algorytmu Luhna
 * @author kodatnik.blogspot.com
 */
public class AlgorytmLuhna {

 public static boolean czyPoprawna(String liczba){
  // zmienne przechowujące odpowiednie sumy
  int sumaParzystych = 0, sumaNieparzystych = 0;

  // odwracamy liczbę dla uproszczenia obliczeń
  String odwroconaLiczba = new StringBuilder(liczba).reverse().toString();
        
  // pętla dla poszczególnych cyfr
  for(int i = 0 ;i < odwroconaLiczba.length(); i++){

   // zamieniamy znak cyfry na wartość liczbową
   int cyfra = Integer.parseInt(odwroconaLiczba.substring(i, i + 1));
            
   // cyfra na pozycji nieparzystej
   if(i % 2 == 0) { 
    // zwiększamy sumę 
    sumaNieparzystych += cyfra;
   } 
   // cyfra na pozycji parzystej
   else {  
    // podwajamy cyfrę
    cyfra = cyfra * 2;
                
    // jeśli wynik większy od 9 to sumujemy cyfry wyniku
    if (cyfra > 9) cyfra = (cyfra%10)+1;

    // zwiększamy sumę
    sumaParzystych += cyfra;
   }
  }
  // zwracamy prawdę lub fałsz w zależności od wyniku modulo 10
  return (sumaParzystych + sumaNieparzystych) % 10 == 0;
 }

 public static void main(String[] args) {
  System.out.println(czyPoprawna("4853928344613904"));
  System.out.println(czyPoprawna("4408041234567893"));
 }
}

Uruchomiona aplikacja:

false
true

Czyli pierwsza liczba jest niepoprawna, a druga poprawna (oczywiście według algorytmu Luhna).