|
Mirzo ulug’bek nomidagiVI BOB. NOSIMMETRIK ALGORITMLAR
|
səhifə | 25/93 | tarix | 20.10.2023 | ölçüsü | 0,67 Mb. | | #128930 |
| KRIPTOGRAFIK USULLAR OQUV QOLLANMA
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:
a=b bo‘lsa, (a,b)=a yoki (a,b)=b.
a>b bo‘lsa, a=bq+r, bu yerda 0< r
b=rq1+r1 bajarilib, bu yerda 0< r11=0 bo‘lsa, (a,b)=r bo‘lib algoritm to‘xtaydi, aks holda algoritm davom etadi.
r=r1q2+r2 bajarilib, bu yerda 0< r21, r2=0 bo‘lsa, (a,b)=r2 bo‘lib algoritm to‘xtaydi, aks holda algoritm davom etadi. Ushbu jarayon chekli qadamdan so‘ng tugaydi.
Dostları ilə paylaş: |
|
|