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


-kadam. –soni ikkilik sanoq sistemasiga o‘tkaziladi: 2 bu yerda yoki va . 2-kadam


Download 99.74 Kb.
bet2/5
Sana08.10.2023
Hajmi99.74 Kb.
#1695298
1   2   3   4   5
1-kadam. –soni ikkilik sanoq sistemasiga o‘tkaziladi:
2
bu yerda yoki va .
2-kadam. qiymatni yuklaymiz.
3-kadam. Barcha va qiymatlar uchun


4-kadam . 3-qadamning oxirgi natijasi r0 = ae (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 rk=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, .

Download 99.74 Kb.

Do'stlaringiz bilan baham:
1   2   3   4   5




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling