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

1-kadam. –soni ikkilik sanoq sistemasiga o‘tkaziladi:
₂
bu yerda yoki va .
2-kadam. qiymatni yuklaymiz.
3-kadam. Barcha va qiymatlar uchun


4-kadam . 3-qadamning oxirgi natijasi r₀ = a^e (mod n) biz qidirayotgan yechim deb e’lon qilinadi.


Misol-1. – qoldiqni hisoblang.
Yechish: , bu sonni ikkilik sanoq sistemasiga o‘tkazamiz:

Ya’ni ,
Demak, algoritm qadamiga muvofiq:
,
Qiymatlar quyidagi qoida bo‘yicha hisoblanadi:

javob

Evklid algoritmi
Asimmetrik kriptotizimlar zarur parametrlarni topish va tanlashda ikkita sonning eng katta umumiy bo‘luvchisini topish masalasi bilan to‘qnash kelamiz. Masalan RSA, EL-GAMAl algoritmlari uchun , -tub sonlari, -parametr va boshqalar. Ana shu maqsadda, bu ishni amalga oshiruvchi algoritm haqida fikr yuritamiz.
Ikkita natural sonning EKUB – ni topishda Evklid algoritmi deb ataluvchi usuldan foydalaniladi. Bu algoritm qadamlari esa quyidagicha:

1. 
   bo‘lsa, .
   
2. 
   Agar bo‘lib, masalan bo‘lsa, u holda soni soniga bo‘linadi:
   

, b (1)
bunda bo‘lsa, algoritm o‘z ishini to‘xtatib, bo‘ladi.
Agarda bo‘lsa, algoritm o‘z ishini davom ettiradi.
3. soni ga bo‘linadi:
,
bunda bo‘lsa, algoritm o‘z ishini to‘xtatib, bo‘ladi. Agarda bo‘lsa, algoritm o‘z ishini davom ettiradi.
4 qoldiq – ga bo‘linadi:
,
Ushbu jarayon chekli qadamdan so‘ng tugaydi, chunki ……. lardan ko‘rinadiki:

shartlarni qanoatlantiradi, bu degani esa chekli «k» qadamdan so‘ng r_k=0 bo‘ladi.
Shunda algoritm o‘z ishini tugatib,

deb eьlon qilinadi
Misol 1. , sonlarining topilsin.
Yechish. Dastlabki sistema juftlikdir. , bo‘lgani uchun algoritmning birinchi qadami : , ,
Miqdorlarning keyingi sistemasi: bo‘ladi va qoldiq bo‘lgani uchun ikkinchi qadami:
, natijada miqdorlarning uchinchi sistemasi hosil bo‘ladi, bo‘lgani uchun algoritmning uchinchi qadami:
natijada miqdorlarning to‘rtinchi sistemasi hosil bo‘ladi.
Nihoyat bo‘lgani uchun algoritmning to‘rtinchi qadami boshlanadi:
, bu yerda qoldik nol chiqdi, natijada miqdorlarnig oxirgi sistemasi hosil bo‘ladi:

Bu jarayonlarni shartli ravishda quyidagicha ifodalash mumkin:

Demak, .