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

Վիքիպեդիայից՝ ազատ հանրագիտարանից

Լունայի ալգորիթմ (անգլ.՝ 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