Luhnův algoritmus
Luhnův algoritmus je jednoduchý algoritmus kontrolního součtu čísel, používaný dnes při kontrole platnosti řady identifikačních čísel. Jako kontrolní mechanismus se nesnaží být kryptografickou hašovací funkcí a není odolný vůči cíleným útokům, jeho úkolem je pomoci při detekci náhodných chyb.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/4/41/Napis_na_voze_20080506.jpg/220px-Napis_na_voze_20080506.jpg)
Používá se například pro čísla kreditních karet, identifikaci železničních vozidel, čísla IMEI, nebo pro variabilní symboly přidělované organizacím od roku 2009 Českou správou sociálního zabezpečení.[1] Existuje i varianta pro nečíselné řetězce, Luhnův algoritmus modulo N.
Algoritmus vymyslel Hans Peter Luhn z IBM a popsal jej v patentu 2 950 048 amerického patentového úřadu podaném 6. ledna 1954 a schváleném 23. srpna 1960.[2] Dnes již algoritmus žádným patentem chráněn není a využívá se v mnoha aplikacích, je například součástí specifikace ISO/IEC 7812.
Algoritmus
editovatAlgoritmus je nezávislý na délce čísla (principiálně stačí dvouciferný řetězec).
Autorita přidělující identifikační číslo stanoví Luhnovým algoritmem kontrolní číslici a přidá ji na jeho pravý konec.
Při kontrole správnosti takového identifikačního čísla, například při jeho neautomatizovaném odečtu, se potom postupuje v těchto třech krocích:
- Pro každou druhou číslici (bráno zprava, tedy se netýká kontrolní číslice) spočítáme její dvojnásobek.
- Ciferné součty získaných dvojnásobků sečteme se zbývajícími číslicemi.
- Pokud nám vyšel výsledek končící nulou (tedy číslo, jehož zbytek po dělení 10 je nula), původní číslo prošlo testem, jinak jím neprošlo.
Příklad
editovatIdentifikační údaj „21 RIV 54 CZ-ČD 5555 774–8“ na vozidle z ilustračního obrázku by byl kontrolován takto:
- Vlastní součástí identifikace jsou jen číslice, k ostatním znakům se nepřihlíží, vstupem algoritmu je tedy číslo 215455557748.
- Zdvojnásobením každé druhé číslice zprava získáme: (4×2) = 8, (7×2) = 14, (5×2) = 10, (5×2) = 10, (5×2) = 10, (2×2) = 4; (dvouciferné) výsledky nahradíme jejich cifernými součty.
- Sečtením ciferných součtů s číslicemi na ostatních pozicích získáme (zprava): 8 + (8) + 7 + (1 + 4) + 5 + (1 + 0) + 5 + (1 + 0) + 4 + (1 + 0) + 1 + (4) = 50
- Zbytek po dělení deseti je nula, číslo je tedy platné.
Implementace
editovatNapříklad v Pythonu může vypadat zápis algoritmu takto:
def luhn_check(num):
rpos = sum_ = 0
while num:
num, c = divmod(num, 10)
if rpos % 2:
sum_ += sum([int(x) for x in str(2 * c)])
else:
sum_ += c
rpos += 1
return sum_ % 10 == 0
Odkazy
editovatReference
editovat- ↑ Oznámení o zavedení nového variabilního symbolu [online]. Česká správa sociálního zabezpečení [cit. 2010-05-05]. Dostupné v archivu pořízeném dne 2010-04-13.
- ↑ Computer for verifying numbers. Původce vynálezu: Hans P. LUHN. United States, Patent Office. Patentový spis US2950048. 1960-08-23. Dostupné: <online> [cit. 2023-07-28]. (anglicky)