1-amaliy mashg’ulot kriptografik masalalarni yechishda arifmetik hisoblashlarni o’rganish ishning maqsadi

1-AMALIY MASHG’ULOT


KRIPTOGRAFIK MASALALARNI YECHISHDA ARIFMETIK HISOBLASHLARNI O’RGANISH

Ishning maqsadi: Kriptografiyada ishlatiladigan matematik o‘zgarishlarning matematik asoslarini o‘rganish.

1. 
   QISQACHA NAZARIY MA’LUMOTLAR
   

1. 
   Eng katta umumiy bo‘luvchi
   

a₁, a₂, ..., a_n butun sonlarning eng katta umumiy bo‘luvchisi (EKUB, yoki ingl. - Greatest Common Divider - GCD) deb ushbu sonlarning shunday umumiy musbat bo‘luvchisiga aytiladiki, bunda ikki yoki bir necha natural sonlarning har biriga boʻlinuvchi eng kichik musbat son tushuniladi.

EKUBni topish uchun sonlardan har biri tub ko’paytuvchilarga ajratiladi va eng kichik ko’rsatkichli hamma umumiy ko’paytuvchilar yozib chiqiladi.
Misol:
I kkita son berilgan: 504, 660.

Misol uchun: EKUB(504,660)=12; EKUB(27,44)=1; EKUB(120,66)=6.
Dasturlashda bu usuldan foydalanish noqulay va nisbatan sekin. Chunki, avval, har bir sonni tub ko'paytuvchilarga ajratish kerak, keyin har biridan umumiylarini topib chiqish kerak. Shuning uchun dasturlashda boshqa samaraliroq va tezroq usul bo'lgan Yevklid algoritmidan foydalaniladi.


1.2. Yevklid algoritmi


Yevklid algoritmi-ikkita butun sonning eng katta umumiy bo’luvchisini topish, shuningdek ikkita o’lchovdosh kesmaning umumiy o’lchovini topish usuli. Ikkita musbat butun sonning eng katta umumiy bo’luvchisini topish uchun avvalo katta sonni kichik songa bo’lish, so’ngra kichik sonni katta sonning qoldig’iga, keyin esa birinchi qoldiqni ikkinchi qoldiqqa va hakoza bo’lish lozim. Bu jarayondagi noldan farqli oxirgi qoldiqqa berilgan sonlarning eng kata umumiy bo’luvchisi bo’ladi.
Yevklid algoritmi qadamlari:

1. 
   Ikkita sondan kattasini kichigiga bo’lib qoldiq olamiz.
   
2. 
   Ularni o’rnini almashtiramiz
   
3. 
   1- va 2-qadamlarni sonlardan biri nol bo’lib qolguncha davom ettiramiz
   
4. 
   Qolgan son shu ikki son uchun EKUB bo’ladi.
   

Ikki sonning eng katta umumiy bo‘luvchisini topish uchun foydalaniladi.
EKUB(a, b) = EKUB(b, r), bunda
a = b∙q + r.
Misol: EKUB(22, 8) = ?
22 = 8*2 + 6
(22, 8) = (8, 6)
8 = 6*1 + 2
(8, 6) = (6, 2)
6 = 2*2 + 2
(6, 2) = (2, 2)
2 = 2*1 + 0
Olindi: EKUB(22, 8) = 2.