Լունայի ալգորիթմ

Լունայի ալգորիթմ
Տեսակ	ալգորիթմ և check digit?
Անվանված է	Hans Peter Luhn?

Լունայի ալգորիթմ (անգլ.՝ Luhn algorithm) - ISO/IEC 7812 ստանդարտի կրեդիիտային քարտի համարի հսկիչ թվանշանի հաշվարկման ալգորիթմ։ Այն չի հանդիսանում կրիպտոգրաֆիկ միջոց, այլ առաջին հերթին նախատեսված է սխալների հայտնաբերման համար, որոնք առաջացել են տվյալների ոչդիտավորյալ աղավաղման արդյունքնում (օրինակ, ձեռքով կրեդիտային քարտի համարի մուտքագրման ժամանակ, հեռախոսով սոցիալական ապահովագրության համարների մասին տվյալների ընդունման ժամանակ և այլն)։ Այն հնարավորություն է տալիս որոշ աստիճանի վստահությամբ դատողություն անել թվերի խմբում սխալի բացակայության մասին, սակայն թույլ չի տալիս այն տեղայնացնել և հայտնաբերված անճշտությունը վերացնել։

Ալգորիթմը մշակվել է IBM ֆիրմայի աշխատակից Հանս Պիտեր Լունայի կողմից, նկարագրվել է 1954 թվականին, արտոնագիր է ստացվել 1960 թվականին։

Հսկիչ թվի հաշվարկման առավել տարածված կիրառումներն են՝

• բանկային բոլոր քարտերի համարները,
• որոշ ոչզեղջային քարտերի համարները,
• սոցիալական ապահովագրության կոդերը,
• IMEI – կոդերը,
• ռուսական երկաթգծերի վագոնի միասնական 8-նիշ համարների հսկիչ թվի հաշվարկ։

Ներկայումս ալգորիթմը հանդիսանում է հանրային սեփականություն։

Առավելություններն ու թերությունները

Ի շնորհիվ իրականացման հեշտության ալգորիթմը գրավում է մինիմալ հաշվարկային հզորություն, հաշվարկի հմտությունների առկայության դեպքում հաշվարկը կարող է կատարվել մտքում։ Միևնույն ժամանակ, Լունայի ալգորիթմը հնարավորություն է տալիս միայն հայտնաբերել սխալները տվյալների խմբում, և այն էլ ոչ բոլոր դեպքերում։ Մի թվի անճշտությունը հայտնաբերվում է։ Պրակտիկորեն հայտնաբերվում են գրեթե բոլոր հաջորդական զույգ թվանշանների տեղափոխությունները (բացառությամբ՝ 09 ↔ 90)։ Չեն կարող հայտնաբերվել երկու հաջորդական թվերի որոշ աղավաղումներ, ինչպես 22 ↔ 55, 33 ↔ 66 և 44 ↔ 77։ Ալգորիթմը տեղեկություն չի տալիս առաջացած սխալի տեղի և բնույթի մասին։

Ալգորիթմը կարող է օգտագործվել ցանկացած երկարության թվերի հաջորդականության համար, սակայն այդ դեպքում պետք է հաշվի առնել, որ մեծ երկարությամբ թվերի համար հավանական է միաժամանակ մի քանի անճշտությունների առկայություն։ Այդպիսի որոշակի սխալներ կարող են բերել ոչճիշտ եզրակացության, որ Լունայի ալգորիթմով հաշվարկված հսկիչ թիվը հաստատում է տվյալների անփոփոխությունը։

Հսկիչ թվանշանի ստուգման ալգորիթմը

Պարզեցված ալգորիթմ

1. Սկսելով 1-ով (այսինքն՝ 1, 3, 5, 7, 9, . . .) ձախից առաջին թվից այն դեպքում, եթե թվում թվանշանների քանակը զույգ է (ինչպես այս օրինակում, որտեղ այն հավասար է 16-ի), իսկ եթե թվանշանների քանակը կենտ է, այդ դեպքում 1-ով սկսում ենք երկրորդ թվից (այսինքն՝ 2, 4, 6, 8, . . . ) կատարվում է ստուգում, եթե 2•x > 9, այդ դեպքում արտադրյալից հանվում է 9, հակառակ դեպքում 2•x արտադրյալը թողնում ենք առանց փոփոխության։

Օրինակ,

4 5 6 1   2 6 1 2   1 2 3 4   5 4 6 4
8   12    4   2    2   6    10  12
8   3    4   2    2   6    1   3

2. Այնուհետև բոլոր թվերը գումարվում են։

8+5+3+1 + 4+6+2+2 + 2+2+6+4 + 1+4+3+4 = 57

3. Ստացված թիվը պետք է լինի 10-ի բազմապատիկ (40, 50, 60, 70, . . .)։

Օրինակում վերջին թիվը հսկիչ թվանշանն է։ Որպեսզի համարն ըստ Լունայի ալգորիթմի լինի ճիշտ, հսկիչ թվանշանը պետք է հավասար լինի 7-ի։

4 5 6 1   2 6 1 2   1 2 3 4   5 4 6 7
8   12    4   2    2   6    10  12
8   3    4   2    2   6    1   3

8+5+3+1 + 4+6+2+2 + 2+2+6+4 + 1+4+3+7 = 60

Մշակողի կողմից նկարագրված ինքնատիպ ալգորիթմ

1. Ստուգվող հաջորդականության թվանշանները համարակալվում են աջից ձախ։
2. Թվանշանները, որոնք գտնվում են կենտ տեղերում, մնում են անփոփոխ։
3. Թվանշանները, որոնք գտնվում են զույգ տեղերում, բազմապատկվում են 2-ով։
4. Եթե այդպիսի բազմապատկման արդյունքում ստացվում է 9-ից մեծ թիվ, ապա այն փոխարինվում է միանիշ թվով, որն առաջանում է բազմապատկման արդյունքում ստացված թվի թվանշանների գումարից, այսինքն՝ թվանշան։
5. Ձևափոխման արդյունքում ստացված բոլոր թվանշանները գումարվում են։ Եթե գումարը 10-ի բազմապատիկ է, ապա սկզբնական տվյալները ճիշտ են։

Հսկիչ թվանշանի հաշվման ալգորիթմը

Num[1..N] - ը քարտի համարն է, Num[N] - հսկիչ թվանշանն է։

sum = 0
for i = 1 to N-1 do
 p = Num[N-i]  
 if (i mod 2 <> 0) then
  p = 2*p
  if (p > 9) then 
   p = p - 9
  end if
 end if
 sum = sum + p
next i
//լրացվում է մինչև 10-ը 
sum = 10 - (sum mod 10)
if (sum == 10) then 
 sum = 0
end if
Num[N] = sum