2-Mavzu: Modulyar arifmetika Kriptologiya Kafedrasi katt o‘qit., Mardiyev U. R

2-Mavzu: Modulyar arifmetika

Kriptologiya Kafedrasi

katt.o‘qit., Mardiyev U.R.

Reja:

• Evklid va kengaytirilgan Evklid algoritmi
• Modulyar arifmetika va uning xossalari
• Sonni modul bo‘yicha teskarisni topish
• Katta darajali sonlarni modu bo‘yicha qoldig‘ini topishning effektiv usuli
• Qoldiqlar haqidagi Xitoy teoremasi
• Diafant tenglamalar

Evklid va kengaytirilgan Evklid algoritmi

• Evklid algoritmini quyidagi ta’riflash mumkin:
• va sonlarining eng katta umumiy bo‘luvchisini topish so‘ralgan bo‘lsin. Ushbu holda quyidagi ketma-ketlik amalga oshiriladi:
• . Agar bo‘lsa, u holda ekanligi kelib chiqadi va bo‘ladi.
• Agar bo‘lsa ni ga bo‘lib quyidagi tenglikni qanoatlantiradigan va butun sonlarga ega bo‘lamiz

. Agar bo‘lsa jarayon to‘xtaydi, ask holda oldingi qadamdek davom etadi

• Ushbu jarayon qoldiq ga teng bo‘maguncha davom etadi. Aytaylik qadamda ga bo‘lindi va qoldiq ga teng bo‘lsa, ushbu hol uchun tengliklar quyidagi ko‘rinishda bo‘ladi:
• .
• .
• .
• .

•  

Evklid va kengaytirilgan Evklid algoritmi

• Hosil bo‘lgan nolga teng bo‘lagan qoldiqni ga teng deb ta‘kidlash mumkin bo‘ladi. Buni isboti quyidagi Lemmaga asoslanadi:
• Agar bo‘lsa, u holda .
• Misol: ni Evklid algoritmi bo‘yicha hisoblash kerak bo‘lsin.
• Demak ga tent bo‘ladi.

•  

Evklid va kengaytirilgan Evklid algoritmi

• Evklid algoritmidan judayam ajoyib fakt kelib chiqadi: ni a va b ning chiziqli birikmasi sifatida ifodalanish mumkin. Ya’ni

bo‘ladigan va butun sonlar mavjud.

• Masalan:
• va ni topish usuli kengaytirilgan Evklid algoritmi deyiladi.
• ni toppish uchun dastlab Evklid algoritmidan foydalaniladi so‘ng, kengaytirilgan Evklid algoritmini amalga oshirish oson bo‘ladi.