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
edytujAlgorytm ten wygląda następująco:
- Dla każdej pozycji cyfry określone zostają wagi (mnożniki). Najczęściej jest to 2 dla pozycji nieparzystych, 1 dla parzystych.
- 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.
- Jeśli w wyniku mnożenia otrzymano liczbę dwucyfrową, dodaje się cyfry do siebie, otrzymując liczbę jednocyfrową.
- Dodaje się wszystkie otrzymane liczby do siebie.
- Wykonuje się operację mod 10 na otrzymanej sumie (pozostawia się jedynie cyfrę jedności).
- 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.
- 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
edytujDana 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
edytujNastę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
edytuj- 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.