Algorytm Luhna

Algorytm Luhna

Algorytm Luhna jest metodą służącą do weryfikacji poprawności wprowadzonego numeru. Znajduje zastosowanie m.in. w walidacji numerów kart kredytowych oraz innych ciągów liczbowych. Jego nazwa pochodzi od Hansa Petera Luhna (1896–1964), niemieckiego naukowca z IBM, który wynalazł mechaniczne urządzenie umożliwiające sprawdzanie poprawności numerów z cyfrą kontrolną.

Na końcu danego ciągu cyfr dodawana jest cyfra kontrolna, która pozwala ustalić, czy wcześniejszy ciąg cyfr został poprawnie wprowadzony. Algorytm ten potrafi wykryć błędy związane z pojedynczą cyfrą lub zamianą miejscami sąsiednich cyfr. Jednak jego główną słabością jest brak możliwości wykrycia zamiany sekwencji 90 na 09 oraz odwrotnie. Ponadto algorytm nie identyfikuje zamian par cyfr (takich jak 22 ↔ 55, 33 ↔ 66 oraz 44 ↔ 77). W rezultacie mnożenie przez 2 co drugiej cyfry sprawia, że algorytm nie wykryje zamian cyfr znajdujących się w niesąsiednich pozycjach, np. w przypadku 1104942 i 1104249.

Algorytm Luhna może być również stosowany do alfanumerycznych ciągów, po przekształceniu liter ABC … XYZ na odpowiadające im ciągi cyfr 10 11 12 … 33 34 35. Cyfra kontrolna mieści się w zakresie 0..9. Istnieje także rozszerzona wersja algorytmu Luhna znana jako Luhn mod N algorithm, która jest wykorzystywana do dowolnych ciągów alfanumerycznych. W tym przypadku cyfra, lub bardziej ogólnie, znak kontrolny, należy do zbioru N dozwolonych znaków.

Dane podstawowe

Algorytm ten można opisać w następujących krokach:

  • Dla każdej cyfry ustala się wagi (mnożniki), najczęściej 2 dla pozycji nieparzystych i 1 dla parzystych.
  • Każdą cyfrę mnoży się przez odpowiadającą jej wagę, zaczynając od prawej do lewej. Przy obliczaniu cyfry kontrolnej ostatnia pozycja traktowana jest jako parzysta, podczas gdy przy sprawdzaniu – jako nieparzysta.
  • Jeśli wynik mnożenia to liczba dwucyfrowa, dodaje się jej cyfry, aby uzyskać cyfrę jednocyfrową.
  • Wszystkie otrzymane liczby sumuje się.
  • Na uzyskanej sumie wykonuje się operację mod 10 (zostaje jedynie cyfra jedności).
  • Jeśli wynikowa cyfra nie jest równa 0, odejmuje się ją od 10, co daje cyfrę kontrolną, którą dodaje się do liczby.
  • Weryfikacja poprawności liczby polega na zastosowaniu kroków 1-5 na całej liczbie (wraz z cyfrą kontrolną). Jeśli liczba jest poprawna, wynik powinien wynosić zero.

Przykład

Rozważmy liczbę 92480_.

Wykonujemy mnożenie z wykorzystaniem odpowiednich wag. Licząc od lewej do prawej, pierwsza pozycja jest nieparzysta (zostawiamy miejsce na cyfrę kontrolną). W nawiasach kwadratowych 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 (dwucyfrowej) sumujemy, otrzymując 9.

Sumujemy wszystkie uzyskane liczby: 9 + 2 + 8 + 8 + 0 = 27.

Wykonujemy operację mod 10: 27 mod 10 = 7.

Skoro 7 ≠ 0, obliczamy 10 – 7 = 3.

Cyfra kontrolna 3 jest „dodawana” do liczby, co daje 924803.

Sprawdzając poprawność wynikowej liczby, stosujemy ten sam algorytm.

Określamy wagi pozycji parzystych i nieparzystych 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

Sumujemy otrzymane liczby: 9 + 2 + 8 + 8 + 0 + 3 = 30.

Wykonujemy operację mod 10: 30 mod 10 = 0.

Wynik jest zerem, co oznacza, że liczba jest poprawna.

Załóżmy, że pomyłka polega na przestawieniu dwóch cyfr, otrzymując 928403.

Sprawdzamy poprawność:

  • [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

Sumujemy uzyskane liczby: 9 + 2 + 7 + 4 + 0 + 3 = 25.

Wykonujemy operację mod 10: 25 mod 10 = 5.

Wynik nie jest zerem, co oznacza, że liczba jest błędna.

Implementacja

Poniższa funkcja w Visual Basic for Application (VBA) zwraca cyfrę kontrolną Luhna dla podanego ciągu. Jeśli dodasz ją do parametru, uzyskasz pełny poprawny kod. Funkcja ta była testowana dla numerów IMEI telefonów. Istnieje również funkcja w C#, która sprawdza poprawność liczby, zwracając true, jeśli podana tablica cyfr jest prawidłową liczbą Luhna, a false w przeciwnym przypadku.

Inna funkcja w C# generuje losową liczbę zakończoną cyfrą kontrolną obliczoną za pomocą algorytmu Luhna.

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.

Przeczytaj u przyjaciół: