Algorytm Luhna – jeden z najczęściej wykorzystywanych algorytmów służących do sprawdzania poprawności wpisania danej liczby. Jest on używany m.in. do walidacji numerów kart kredytowych, ciągów liczbowych, itd. Nazwa algorytmu pochodzi od nazwiska Hansa Petera Luhna (1896–1964), niemieckiego naukowca pracującego w IBM.

Na końcu liczby doklejana jest cyfra kontrolna pozwalająca sprawdzić, czy poprzedzający ją ciąg cyfr jest wpisany poprawnie. Algorytm dopuszcza wykrycie pomyłki pojedynczej cyfry albo większości zamian kolejności sąsiednich cyfr. Główną słabością jest nie wykrywanie zamiany sekwencji 90 na 09 oraz odwrotnie.

Dane podstawowe

Algorytm ten wygląda następująco:

1. Dla każdej pozycji cyfry określone zostają wagi (mnożniki). Najczęściej jest to 2 dla pozycji nieparzystych, 1 dla parzystych.
2. Każdą cyfrę liczby mnożymy przez odpowiadającą jej wagę od prawej do lewej. Przy obliczaniu cyfry kontrolnej przyjmujemy, że ostatnia pozycja jest parzysta, a przy sprawdzaniu - nieparzysta.
3. Jeśli w wyniku mnożenia otrzymamy liczbę dwucyfrową, dodajemy cyfry do siebie otrzymując liczbę jednocyfrową.
4. Dodajemy wszystkie otrzymane liczby do siebie.
5. Wykonujemy operację mod 10 na otrzymanej sumie (pozostawiamy zaledwie cyfrę jedności).
6. Następnie, jeśli otrzymana cyfra nie równa się 0, odejmujemy ją od 10. Otrzymujemy cyfrę kontrolną, która jest "doklejana" do liczby.
7. Sprawdzenie poprawności liczby przebiega się poprzez zastosowanie na całej liczbie (łącznie z cyfrą kotrolną) kroków 1-5. Jeżeli liczba jest poprawna otrzymamy w wyniku zero.

Przykład

Mamy liczbę 92480_.

• Wykonujemy mnożenie przez odpowiednie wagi. Od lewej do prawej, pierwsza pozycja jest nieparzysta (inaczej mówiąc - zostawiamy wolne miejsce na cyfrę kontrolną). W nawiasie kwadratowym podano indeks pozycji.

[5] 9 * 2 = 18

[4] 2 * 1 = 2

[3] 4 * 2 = 8

[2] 8 * 1 = 8

[1] 0 * 2 = 0

• Cyfry liczby 18 (jako dwucyfrowej) dodajemy do siebie, otrzymując 9.
• Otrzymane liczby dodajemy do siebie: 9 + 2 + 8 + 8 + 0 = 27.
• Wykonujemy operację mod 10: 27 mod 10 = 7.
• 7<>0, więc wykonujemy operację 10 – 7 = 3.
• Cyfrę kontrolną 3 "doklejamy" do liczby, otrzymując 924803.

Sprawdzenie poprawności wynikowej liczby opiera się na zastosowaniu tego samego algorytmu.

Wagi pozycji parzystych oraz nieparzystych ponownie określamy licząc od prawej do lewej - pierwsza pozycja jest parzysta.

[5] 9 * 2 = 18 (suma cyfr: 9)

[4] 2 * 1 = 2

[3] 4 * 2 = 8

[2] 8 * 1 = 8

[1] 0 * 2 = 0

[0] 3 * 1 = 3

• Dodajemy otrzymane liczby do siebie: 9 + 2 + 8 + 8 + 0 + 3 = 30.
• Wykonujemy operację mod 10: 30 mod 10 = 0.
• Otrzymany wynik jest zerem czyli liczba jest poprawna

Przypuśćmy, że w zapisie jest błąd polegający na przestawieniu dwóch cyfr: 928403.

Sprawdzenie poprawności:

[5] 9 * 2 = 18 (suma cyfr: 9)

[4] 2 * 1 = 2

[3] 8 * 2 = 16 (suma cyfr: 7)

[2] 4 * 1 = 4

[1] 0 * 2 = 0

[0] 3 * 1 = 3

• Dodajemy otrzymane liczby do siebie: 9 + 2 + 7 + 4 + 0 + 3 = 23.
• Wykonujemy operację mod 10: 23 mod 10 = 3.
• Otrzymany wynik nie jest zerem czyli liczba jest błędna

Implementacja

Następująca funkcja C# służy do sprawdzania poprawności liczby, zwraca true, jeśli dana tablica cyfr jest prawidłową liczbą Luhna, a false, jeśli nie.

  bool CheckNumber(int digits)
  {
    int sum = 0;
    bool alt = false;
    for(int oraz = digits.Length - 1; oraz >= 0; i--)
    {
      int temp = digitsi;
      if(alt)
      {  
        temp *= 2;
        if(temp > 9)
        {
          temp -= 9; //równoważne dodaniu cyfr do siebie np. 1+6 = 7, 16-9 = 7
        }
      }
      sum += temp;
      alt = !alt;
    }
    return sum % 10 == 0;
  }

Następująca funkcja (w C#) generuje losową liczbę zakończoną cyfrą kontrolną obliczoną wg. algorytmu Luhna.

  int CreateNumber(int length)
  {
    Random random = new Random();
    int digits = new intlength;
    for(int oraz = 0; oraz < length - 1; i++)
    {
      digitsi = random.Next(10);
    }
    int sum = 0;
    bool alt = true;
    for(int oraz = length - 2; oraz >= 0; i--)
    {
      int temp = digitsi;
      if(alt)
      {  
        temp *= 2;
        if(temp > 9)
        {
          temp -= 9; //równoważne dodaniu cyfr do siebie np. 1+6 = 7, 16-9 = 7
        }
      }
      sum += temp;
      alt = !alt;
    }
    int modulo = sum % 10;
    if(modulo > 0)
    {
      modulo = 10 - modulo;
    }
    digitslength-1 = modulo;
    return digits;
  }

Linki zewnętrzne

• Patent Luhna Nr. 2950048 Computer for Verifying Numbers, Hans P. Luhn, August 23, 1960.