Bajardi: 414-21 guruh talabasi Choriyev Fazliddin Tekshirdi: Safoyev Nuriddin Toshkent – 2022

O’ZBEKISTON RESPUBLIKASI AXBOROT TEXNOLOGIYALARI VA KOMMUNIKATSIYALARINI RIVOJLANTIRISH VAZIRLIGI
MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI

“TELEKOMMUNIKATSIYA TEXNOLOGIYALARI” fakulteti

MUSTAQIL ISH

Bajardi: 414-21 guruh talabasi
Choriyev Fazliddin
Tekshirdi: Safoyev Nuriddin

Toshkent – 2022

MUNDARIJA

MODUL ARFMETIKASI TUSHUNCHASI
Ochiq kalitli kriptotizimlarni chuqur o’rganishdan oldin ularning asosi hisoblangan sonlar nazariyasi bilan yaqindan tanishib chiqish muhim hisoblanadi. Ochiq kalitli kriptotizimlar asosan modul arifmetikasiga asoslangani bois, dastlab ularga to’xtalib o’tiladi.
Har qanday butun sonni 𝑆𝑆_∈ 𝑧𝑧 ga bo’lsak, bu songa tayin bir qoldiq to’g’ri keladi. Masalan, bo’lib, unda qoldiq 1 ga va butun qism 2 ga teng bo’ladi. Kriptografiyada 𝑎𝑎 sonni 𝑎𝑎 songa bo’lgandagi qoldiq 𝑆𝑆 ga teng bo’lsa, u quyidagicha belgilanadi: 𝑎modb ≡ r . Dasturlash tillarida esa a%b kabi belgilanadi.

Bundan tashqari ochiq kalitli kriptografiyada sonning modul bo’yicha teskarisini hisoblash muhim hisoblanadi. Masalan, odatiy matematikada 𝑎 sonining teskarisi 1/𝑎 ga teng bo’ladi. Modul arifmetikasida esa 𝑎 sonining 𝑛 modul bo’yicha teskarisi a^-1modn ko’rinishida belgilanadi. Odatiy matematikada sonni uning teskarisiga ko’paytmasi birga teng bo’lgani kabi, modul arifmetikasida ham soning uning teskarisiga moduldagi ko’paytmasi birga teng bo’ladi. Ya’ni, a^-1modn=b bo’lsa, u holda (a*b)modn=1 tenglik o’rinli bo’ladi.
Izoh. Kriptografiyada modul sifatida (ya’ni, bo’luvchi) faqat tub sonlardan foydalanish talab etiladi. Ya’ni, amodn tenglikdagi n har doim tub bo’lishi talab etiladi.
Misol tariqasida, 3 sonining 7 maydondagi teskarisini topish talab etilsin. Ya’ni, 𝑥 ni topish talab etilsin: 3^-1mod7=x. Yuqoridagi tenglik (3∗𝑥)mod7=1 dan foydalanib, 𝑥 ning o’rniga son qo’yib natijani hisoblash mumkin. Lekin ushbu jarayon ko’p vaqt talab etadi (ayniqsa katta sonlarda juda ham ko’p vaqt talab etiladi).
Ushbu muammoni yechishning ko’plab usullari mavjud bo’lib, quyida ulardan biri bo’lgan qoldiqlar to’g’risidagi Yevklidning kengaytirilgan algoritmidan foydalanib yechish usuli keltirilgan.