Wpisany przez Tomasz Lubiński,
03 kwietnia 2007 00:13
Algorytm Luhn'a zwany inaczej algorytmem mod 10 jest przykładem prostej sumy kontrolnej
używanej powszechnie w różnych numerach identyfikacyjnych takich jak na przykład numery
kart kredytowych, numer IMEI. Metodę tą stworzył naukowiec IBM Hans Peter Luhn w celu
wykrywania przypadkowych błędów w zabezpieczonych numerach. Numery takie mają następującą
strukturę XXXXXXXC, gdzie XXXXXXX to numer identyfikacyjny (o dowolnej
liczbie cyfr), a C to cyfra kontrolna. Algorytm sprawdzania poprawności liczby
zabezpieczonej tą metodą przebiega następująco:
Sprawdzimy czy numer IMEI: 353275011731396 jest prawidłowy.
Najpierw użyjemy tabeli powyżej do zamiany cyfr na pozycjach parzystych - licząc od prawej strony.
Czyli otrzymamy: 313471021532396.
Teraz dodajemy do siebie wszystkie cyfry, opórcz cyfry kontorlnej.
3 + 1 + 3 + 4 + 7 + 1 + 0 + 2 + 1 + 5 + 3 + 2 + 3 + 9 + 6 = 50.
Wynik jest podzielny przez 10, zatem podany numer IMEI jest prawidłowy.
Zadaniem cyfry kontrolnej jest dopełnienie tak całej sumy by całość była podzielna przez 10. Jak zatem obliczyć ją dla podanego numeru identyfikacyjnego? Zaczynamy podobnie jak przy sprawdzaniu:
Obliczymy cyfrę kontrolną dla innego numeru IMEI: 35328501174149c.
Najpierw użyjemy tabeli powyżej do zamiany cyfr na pozycjach parzystych - licząc od prawej strony.
Czyli otrzymamy: 31348102154249c.
Teraz dodajemy do siebie wszystkie cyfry, opórcz cyfry kontorlnej.
3 + 1 + 3 + 4 + 8 + 1 + 0 + 2 + 1 + 5 + 4 + 2 + 4 + 9 = 47.
Wynik dzielimy modulo 10.
47 mod 10 = 7
Wynik odejmujemy od 10.
10 - 7 = 3
I znów dzielimy modulo 10.
3 mod 10 = 3
Zatem cyfra kontrolna c powinna wynosić 3. Zatem prawidłowy numer IMEI to: 353285011741493.
- zaczynając od cyfry z prawej strony (czyli cyfry kontrolnej) poruszając się w lewą
stronę podwajamy co drugą cyfrę (czyli drugą od prawej, czwartą od prawej, itd..). Jeżeli
podwojona cyfra jest większa lub równa 10, wówczas dodajemy do siebie jej cyfry. Czyli
jeżeli na parzystej pozycji od strony prawej stoi 1 to zamieniamy ją na 2, jeżeli stoi 6 to
zamieniamy ją na 3, bo 6*2=12 i teraz dodajemy cyfry 1+2=3. W praktyce poprostu korzystamy
z gotowej tablicy:
Cyfra Cyfra podwojona Suma cyfr liczby podwojonej 0 0 0+0=0 1 2 0+2=2 2 4 0+4=4 3 6 0+6=6 4 8 0+8=8 5 10 1+0=1 6 12 1+2=3 7 14 1+4=5 8 16 1+6=7 9 18 1+8=9 - dodajemy do siebie wszystkie cyfry
- jeżeli wynik jest podzielny przez 10, to numer jest prawidłowy
Przykład:
Sprawdzimy czy numer IMEI: 353275011731396 jest prawidłowy.
Najpierw użyjemy tabeli powyżej do zamiany cyfr na pozycjach parzystych - licząc od prawej strony.
Czyli otrzymamy: 313471021532396.
Teraz dodajemy do siebie wszystkie cyfry, opórcz cyfry kontorlnej.
3 + 1 + 3 + 4 + 7 + 1 + 0 + 2 + 1 + 5 + 3 + 2 + 3 + 9 + 6 = 50.
Wynik jest podzielny przez 10, zatem podany numer IMEI jest prawidłowy.
Zadaniem cyfry kontrolnej jest dopełnienie tak całej sumy by całość była podzielna przez 10. Jak zatem obliczyć ją dla podanego numeru identyfikacyjnego? Zaczynamy podobnie jak przy sprawdzaniu:
- zaczynając od cyfry z prawej strony (czyli cyfry kontrolnej) poruszając się w lewą stronę podwajamy co drugą cyfrę (czyli drugą od prawej, czwartą od prawej, itd..). Jeżeli podwojona cyfra jest większa lub równa 10, wówczas dodajemy do siebie jej cyfry. Czyli jeżeli na parzystej pozycji od strony prawej stoi 1 to zamieniamy ją na 2, jeżeli stoi 6 to zamieniamy ją na 3, bo 6*2=12 i teraz dodajemy cyfry 1+2=3. W praktyce poprostu korzystamy z przedstawionej już tablicy.
- dodajemy do siebie wszystkie cyfry, z wyjątkiem cyfry kontrolnej
- wynik dzielimy modulo 10 i odejmujemy od 10
- wynik znów dzielimy modulo 10 (to zabezpieczenie gdyby w poprzednim kroku wyszło nam 10)
- otrzymany wynik jest równy prawidłowej cyfrze kontrolnej
Przykład:
Obliczymy cyfrę kontrolną dla innego numeru IMEI: 35328501174149c.
Najpierw użyjemy tabeli powyżej do zamiany cyfr na pozycjach parzystych - licząc od prawej strony.
Czyli otrzymamy: 31348102154249c.
Teraz dodajemy do siebie wszystkie cyfry, opórcz cyfry kontorlnej.
3 + 1 + 3 + 4 + 8 + 1 + 0 + 2 + 1 + 5 + 4 + 2 + 4 + 9 = 47.
Wynik dzielimy modulo 10.
47 mod 10 = 7
Wynik odejmujemy od 10.
10 - 7 = 3
I znów dzielimy modulo 10.
3 mod 10 = 3
Zatem cyfra kontrolna c powinna wynosić 3. Zatem prawidłowy numer IMEI to: 353285011741493.
Implementacje
Autor | Język programowania | Komentarz | Otwórz | Pobierz | Ocena |
Tomasz Lubiński | C/C++ | .cpp | .cpp | ***** / 3 | |
Tomasz Lubiński | Delphi/Pascal | .pas | .pas | ***** / 2 | |
Tomasz Lubiński | Java | .java | .java | ***** / 3 |
Poprawiony: 15 sierpnia 2012 07:11