1- amaliy ish Mavzu: Modulyar arifmetika. Evklid va kengaytirilgan Evklid algoritmi hamda ularning dasturiy ta‘minotini ishlab chiqish. Ishdan maqsad

MISOL 2. Evklid algoritmini qo‘llab
va , - qiymatlar topilsin.
Yevklid algoritmi qadamlariga muvofiq:
, ya’ni
, ya’ni
, ya’ni
, ya’ni
, ya’ni
, ya’ni
demak,

soni 6188 va 4709 sonlarining -deb e’lon kilinadi, ya’ni
.
Kengaytirilgan Evklid algoritmiga ko‘ra:

=?, =? topaylik:
yuqorida keltirilgan ifodani quyidagicha yozib olamiz:





yoki :
,
ya’ni
; demak, =121; = - 159
JAVOB: =121, = - 159.
Berilgan modul buyicha teskari elementni topish
RSA shifrlash algoritmi uchun ochiq kalit «e» soni d –soniga modul (n) bo‘yicha teskari son hisoblanadi.Bu son bizga shu algoritmning 4-qadamini amalga oshirish uchun zarur bo‘ladi. Bu elementni aniqlash usullari haqida muhim tushunchalarni berib o‘tamiz. EL-GAMAL algoritmi qadamlarida esa bu elementga murojat qilinmaydi.
Taьrif. Agar va n butun sonlar o‘zaro tub bo‘lsa, shunday a’ son mavjud bo‘lib,

taqqoslama o‘rinli buladi.
Bu yerda son, -ga modul n bo‘yicha teskari (element)son deyiladi va kabi belgilanadi. Uni hisoblash Eyler funksiyasi yordamida va kengaytirilgan Evklid algoritmidan foydalangan holda amalga oshiriladi.
MISOL 3. , bo‘lsa,

bo‘ladi. U holda shunday son mavjud bo‘lib, tenglik o‘rinli bo‘ladi. Demak, -ni topish kerak.

Bu misolni kengaytirilgan Evklid algoritmi yordamida yechishni ko‘rib chiqamiz.

Berilgan misolga ko‘ra :



qoldiq nol bo‘lgandan oldingi qoldiqdan boshlab teskarisiga qaytsak :

va ekanligini eьtiborga olsak, ifodani
quyidagicha yozishimiz mumkin:

yaьni , bu yerda , , , ( kengaytirilgan Yevklid algoritmi uchun).
Shunday qilib, biz qidirayotgan son esa quyidagiga teng bo‘ladi :

Javob