Luhn-formula

A Luhn-algoritmus vagy Luhn-formula, más néven modulus 10 vagy mod 10 algoritmus azonosító számok ellenőrzésére szolgál. Egyszerű ellenőrzőösszeg-alapú képletről van szó, amit mindenféle azonosító számok ellenőrzésére használnak, úgymint hitelkártyák vagy személyi számok. Az algoritmust Hans Peter Luhn, az IBM egyik tudósa alkotta meg. Szabadalmi kérvényét 1954-ben nyújtotta be, melyet 1960-ban hagytak jóvá.^[1] Az algoritmust engedélyezését követően a hatvanas években a hitelkártya-gyártók alkalmazni kezdték és így hamar ismertté vált.

Az algoritmust, közkincs besorolása miatt is, széles körben használják. Nem szánták kriptográfiai hash függvénynek; csak a véletlenül fellépő hibák (pl. elgépelés) ellen véd, rosszindulatú támadások ellen nem. A hitelkártyák és állami azonosító számok többsége használja ezt az egyszerű eljárást arra, hogy az érvényes számokat megkülönböztesse a véletlen számjegyek csoportjától.

Magyarázat

Az algoritmus létrehoz egy ellenőrző számot, amit rendszerint hozzátesznek a hitelkártya- vagy személyi számhoz, így jön létre a teljes szám. A teljes számnak meg kell felelnie a következő algoritmusnak:

Az utolsó előtti számmal kezdve bal felé haladva kétszerezzük meg minden második szám értékét. Ha 10-nél magasabb számot kapunk, adjuk össze számjegyeit, az így kapott összeget írjuk a régi számjegy helyére. 1111-ből tehát 2121 lesz, 8763-ból pedig 7733, azaz (1+6)7(1+2)3.
Adjuk össze ezeket a számokat (ti. számjegyeket). Az előbb kapott 2121-ből így 6 lesz, 7733-ból 20.
Ha az összeg 0-ra végződik, akkor a szám a Luhn-formula szerint érvényes, egyébként nem az. 1111 tehát nem érvényes, 8763 azonban igen.

Ebben a két példában ha ellenőrzőszámot tennénk a számok elé, akkor 1111 elé egy 4-est kellene tenni, a 8763 elé pedig egy 0-t. Az ellenőrzőszámokat azonban rendszerint a számsor végére teszik, bár ehhez kissé módosítani kell az algoritmust.

Algoritmus

Az algoritmus három lépésben hajtódik végre. Először is, minden második számot, kezdve az utolsó előttivel és bal felé haladva, megkettőzünk. Ha az összeg 9-nél nagyobb, számjegyeit összeadjuk (ami a 10 és 18 közti számoknál annyit jelent, hogy 9-et kivonunk belőle.) Így 2-ből 4 lesz, 7-ből 5. Végül a számjegyeket összeadjuk. Ha a maradék 0, a szám érvényes.

 function checkLuhn(string purportedCC) {
     int sum := 0
     int nDigits := length(puportedCC)
     int parity := nDigits AND 1
     for i from 0 to nDigits {
         int digit := integer(purportedCC[i])
         if (i AND 1) XOR parity ≠ 0
             digitt:= digit × 2
         if digit > 9
             digitt:= digit – 9
         sum := sum + digit
     }
     return (sum % 10) = 0
 }

Példa

Vegyük példának a 456-565-654 számot. Először kettőzzünk meg minden második számot és adjuk össze a számjegyeket az előbb ismertetettek szerint. A következő táblázat ezeket a lépéseket mutatja:

Számjegy	„Duplája”	Számjegyek összege
4	4	4
5	10	1
6	6	6
5	10	1
6	6	6
5	10	1
6	6	6
5	10	1
4	4	4
Összeg:		30

A kapott 30-at elosztjuk 10-zel; a maradék 0, tehát a szám érvényes.

Jegyzetek

↑ „Computer for verifying numbers” (angol nyelven).

További információk

Matematikaportál
Informatikai portál

[1] „Computer for verifying numbers” (angol nyelven).

[1]