Luhnův algoritmus

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

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. Používá se například pro čísla kreditních karet, čí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 je algoritmus volným dílem a je široce využíván, je například součástí specifikace ISO/IEC 7812.

Kontrolní algoritmus[editovat | editovat zdroj]

Vstupem algoritmu je ověřované číslo, k němuž je na pravý konec přidána kontrolní číslice. Ověření probíhá ve třech krocích:

  1. Pro každou druhou číslici (bráno zprava, tedy se netýká kontrolní číslice) spočítáme její dvojnásobek.
  2. Ciferné součty získaných dvojnásobků sečteme se zbývajícími číslicemi.
  3. 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[editovat | editovat zdroj]

Například číslo 49927398716 by bylo kontrolováno takto:

  1. Zdvojnásobením každé druhé číslice zprava získáme: (1×2) = 2, (8×2) = 16, (3×2) = 6, (2×2) = 4, (9×2) = 18
  2. Sečtením ciferných součtů se zbývajícími číslicemi získáme: 6 + (2) + 7 + (1 + 6) + 9 + (6) + 7 + (4) + 9 + (1 + 8) + 4 = 70
  3. Zbytek po dělení deseti je nula, číslo je tedy platné.

Implementace[editovat | editovat zdroj]

Například v Pythonu může vypadat zápis algoritmu takto:

def luhn_check(cc):
    total = 0
    doubleNext = False
    for d in reversed(cc):
        if doubleNext and d:
            total += 2 * int(d) % 9 or 9
        else:
            total += int(d)
        doubleNext = not doubleNext
    return total % 10 == 0

Odkazy[editovat | editovat zdroj]

Reference[editovat | editovat zdroj]

  1. Oznámení o zavedení nového variabilního symbolu [online]. Česká správa sociálního zabezpečení, [cit. 2010-05-05]. Dostupné online.  
  2. 2,950,048 [online]. 1960-8-23, [cit. 2010-05-05]. Dostupné online. (anglicky)