Mirzo ulug’bek nomidagi

VI BOB. NOSIMMETRIK ALGORITMLAR

1. 
   Kriptografiyaning matematik asoslari
   

Natural sonlar to‘plamini N ={1, 2,3, ... } va butun sonlar to‘plamini Z={0,
± 1, ± 2, ±3, ... } ko‘rinishda belgilaymiz. Noldan farqli bo‘lgan a soni va v sonlar Z to‘plamga tegishli, ya’ni a,b eZ bo‘lib, a± 0 bo‘lsin. v soni a soniga butun bo‘linadi deyiladi, agarda shunday s soni mavjud bo‘lib, v=as tenglik bajarilsa. Berilgan a va v sonlarni bo‘luchi butun son, ularning umumiy bo‘luvchisi deyiladi. Umumiy bo‘luvchilar ichida eng kattasi eng katta umumiy bo‘luvchi (EKUB) deyiladi va (a,v) ko‘rinishda belgilanadi. Agarda a va v sonlarning eng katta umumiy bo‘luchisi 1, yani (a,v)=1 bo‘lsa, a va v sonlar O’zaro tub deyiladi. Eng katta umumiy bo‘luvchilarni topishga oid bo‘lgan tasdiqlarni keltiramiz.
Agar v soni a soniga bo‘linsa, u holda bu sonlarnining eng katta umumiy bo‘luvchisi (a,v)=a.
Evklid algoritmi
Bu - ikkita sonning eng katta umumiy bo‘luvchisini topish algoritmi. Evklid bu usulni eramizdan avvalgi 300-yildagi kitobida keltirgan. Algoritm qadamlari quyidagilardan iborat:

1. 
   a=b bo‘lsa, (a,b)=a yoki (a,b)=b.
   
2. 
   a>b bo‘lsa, a=bq+r, bu yerda 0< r
3. 
   b=rq₁+r₁ bajarilib, bu yerda 0< r₁1=0 bo‘lsa, (a,b)=r bo‘lib algoritm to‘xtaydi, aks holda algoritm davom etadi.
   
4. 
   r=r₁q₂+r₂ bajarilib, bu yerda 0< r₂1, r₂=0 bo‘lsa, (a,b)=r₂ bo‘lib algoritm to‘xtaydi, aks holda algoritm davom etadi. Ushbu jarayon chekli qadamdan so‘ng tugaydi.