Algorytm Luhna

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

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 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.

Dane podstawowe[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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ą wg 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[edytuj | edytuj kod]