Algorytm Luhna

Algorytm Luhna – algorytm służący do sprawdzania poprawności wpisania numeru. 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, który opatentował mechaniczne urządzenie do sprawdzania poprawności numerów z cyfrą kontrolną.

Na końcu liczby doklejana jest cyfra kontrolna pozwalająca sprawdzić, czy poprzedzający ją ciąg cyfr jest wpisany poprawnie. Algorytm umożliwia wykrycie pomyłki pojedynczej cyfry lub większości zamian kolejności sąsiednich cyfr. Główną słabością jest niewykrywanie zamiany sekwencji 90 na 09 i odwrotnie. Algorytm nie wykryje także zamian par cyfr (22 ↔ 55, 33 ↔ 66 oraz 44 ↔ 77). Z zasady mnożenia przez 2 co drugiej cyfry wynika, że algorytm nie wykryje zamiany cyfr na niesąsiednich pozycjach, np. 1104942 i 1104249.

Algorytm Luhna stosowany jest także do ciągów alfanumerycznych po zamianie liter ABC ... XYZ na ciągi cyfr 10 11 12 ... 33 34 35. Cyfra kontrolna jest z zakresu 0..9. Używana jest także rozszerzona wersja algorytmu Luhna pod nazwą Luhn mod N algorithm stosowana do dowolnych ciągów alfanumerycznych. Cyfra, a raczej znak kontrolny jest jednym z N dopuszczalnych znaków.

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ży się przez odpowiadającą jej wagę od prawej do lewej. Przy obliczaniu cyfry kontrolnej przyjmuje się, że ostatnia pozycja jest parzysta, a przy sprawdzaniu – nieparzysta.
3. Jeśli w wyniku mnożenia otrzymano liczbę dwucyfrową, dodaje się cyfry do siebie, otrzymując liczbę jednocyfrową.
4. Dodaje się wszystkie otrzymane liczby do siebie.
5. Wykonuje się operację mod 10 na otrzymanej sumie (pozostawia się jedynie cyfrę jedności).
6. Następnie, jeśli otrzymana cyfra nie równa się 0, odejmuje się ją od 10. Otrzymano cyfrę kontrolną, która jest "doklejana" do liczby.
7. Sprawdzenie poprawności liczby odbywa się poprzez zastosowanie na całej liczbie (łącznie z cyfrą kontrolną) kroków 1-5. Jeżeli liczba jest poprawna, otrzyma się w wyniku zero.

Przykład

Dana jest liczba 92480_.

• Wykonuje się mnożenie przez odpowiednie wagi. Od lewej do prawej, pierwsza pozycja jest nieparzysta (inaczej mówiąc – pozostawia się 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) dodaje się do siebie, otrzymując 9.
• Otrzymane liczby dodaje się do siebie: 9 + 2 + 8 + 8 + 0 = 27.
• Wykonuje się operację mod 10: 27 mod 10 = 7.
• 7 ≠ 0, więc wykonuje się operację 10 – 7 = 3.
• Cyfrę kontrolną 3 "dokleja się" do liczby, otrzymując 924803.

Sprawdzenie poprawności wynikowej liczby polega na zastosowaniu tego samego algorytmu.

Wagi pozycji parzystych i nieparzystych ponownie określa się, 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

• Dodaje się otrzymane liczby do siebie: 9 + 2 + 8 + 8 + 0 + 3 = 30.
• Wykonuje się 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

• Dodaje się otrzymane liczby do siebie: 9 + 2 + 7 + 4 + 0 + 3 = 25.
• Wykonuje się operację mod 10: 25 mod 10 = 5.
• Otrzymany wynik nie jest zerem, czyli liczba jest błędna.

Implementacja

Następująca funkcja Visual Basic for Application (VBA) zwraca cyfrę kontrolną Luhna dla podanego w parametrze ciągu. Jeśli dopiszesz ją do parametru uzyskasz pełny poprawny kod. Testowane dla IMEI telefonów.

Private Function Mod10CheckDigit(Barcode As String) As Integer
' funkcja wyznacza cyfrę kontrolną dla otrzymanego ciągu zgodnie z algorytmem Luhn'a (mod 10)
' jeśli chcesz mieć test poprawności całego kodu FullBarcode długości n znaków to użyj wywołania np.:
' CzyKodPoprawny = (Mod10CheckDigit(Left(FullBarcode,n-1))=CInt(Right(FullBarcode,1))
'
    Dim i As Integer
    Dim temp As Integer
    Dim alt As Boolean
    Dim suma As Integer
    Dim wynik As Integer
    
    Barcode = Trim(Barcode)
    suma = 0
    alt = True
    For i = Len(Barcode) To 1 Step -1
        temp = CInt(Mid(Barcode, i, 1))
        If alt Then  'co drugą cyfrę mnożymy przez 2
            temp = temp * 2
            If (temp > 9) Then temp = temp - 9 'sprowadzenie do jednej cyfry
        End If
        suma = suma + temp
        alt = Not alt
    Next i
    
    wynik = suma Mod 10
    If (wynik > 0) Then wynik = 10 - wynik
    Mod10CheckDigit = wynik
End Function

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 i = digits.Length - 1; i >= 0; i--)
    {
      int temp = digits[i];
      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ą przy pomocy algorytmu Luhna.

  int[] CreateNumber(int length)
  {
    Random random = new Random();
    int[] digits = new int[length];
    for(int i = 0; i < length - 1; i++)
    {
      digits[i] = random.Next(10);
    }
    int sum = 0;
    bool alt = true;
    for(int i = length - 2; i >= 0; i--)
    {
      int temp = digits[i];
      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;
    }
    digits[length-1] = modulo;
    return digits;
  }

Linki zewnętrzne

• Patent Luhna Nr 2950048 Computer for Verifying Numbers, Hans P. Luhn, August 23, 1960.
• Weryfikacja i obliczanie cyfry kontrolnej Luhna ISNI, PIC, LEI, ORCID, ISTC, ISO-7064.