1-ma’ruza Mavzu: rsa ochiq kalitli shifrlash algoritmi Reja

Birinchi versiya
Eyler teoremasining birinchi versiyasi Fermatning kichik teoremasining birinchi versiyasiga o‘xshaydi. Agar a va n o‘zaro tub bo‘lsa, u holda o‘rinli.
Ikkinchi versiya
Eyler teoremasining ikkinchi versiyasi Fermatning kichik teoremasining ikkinchi versiyasiga o‘xshash; u soni , bilan o‘zaro tub bo‘lishi kerak degan degan shartni bekor qiladi. Agar bo‘lsa, k — butun son bo‘lsa, u holda  bo‘ladi.
Birinchi versiyaga asoslangan ikkinchi versiyaning zaif dalilini beramiz. (a 1. Agar soni ga yoki sha bo‘linmasa, u holda a va n o‘zaro tub.

2. agar soni p ga bo‘linsa,  , q. Soniga bo‘linmasa.

3. Agar a soni q soniga bshlinsa,  ( ), lekin p soniga bo‘linmasa, ikkinchi holatning isboti bir xil, ammo va o‘zaro bir-biriga bog‘langan.
Eyler teoremasining ikkinchi versiyasi RSA kriptografik tizimida foydalaniladi.
Ilova
Garchi bu ma’ruzada keyinchalik Eyler teoremasining ba’zi amaliy dasturlarini ko‘rib chiqamiz. Teorema ba’zi muammolarni hal qilish uchun juda foydali.
Eksponentlash. Euler teoremasi ba’zan eksponensial muammolarni tezda topish uchun foydalidir
Misol12.15
6²⁴ mod 35 qiymatini toping.
Yechim
ga ega bo‘lamiz
Misol 12.16
20⁶² mod 77. Qiymatini toping
Yechim
Agar ikkinchi versiyaga ko‘ra ni kiritsak, unda:
20⁶² mod 77 = (20 mod 77) mod 77 = (20)(20) mod 77 = 15
Mersenning tub sonlari.
Mersen Mersen raqami deb ataladigan quyidagi formulani taklif qildi. U formulada barcha tub sonlar ro‘yxati borligini aytdi. 
M_p = 2^p–1
Agar yuqoridagi formulada asosiy bo‘lsa, u holda bosh darajaga teng bo‘lishi kerak edi. Yillar o‘tib, Mersen formulasi orqali olingan barcha raqamlarning barchasi ham tub sonlar emasligi isbotlandi. Quyida ba’zi Mersenne raqamlarining ro‘yxati keltirilgan.

Ma’lum bo‘lishicha, M11 bu tub son emas. Biroq, Mersenne formulasi bo‘yicha 41 ta raqam tub ekanligi aniqlandi; Mersennening so‘nggi raqamlaridan biri bu M124036583, eng katta raqam 7 253 733 raqamni o‘z ichiga oladi. Qidiruv davom etmoqda.
Fermat tub sonlarni hosil qiluvchi formulani topishga harakat qildi. Ferma raqamlari uchun quyidagi formula keltirilgan:
Mersenne raqami deb nomlangan formulasidagi raqam bosh raqam bo‘lishi mumkin yoki bo‘lmasligi mumkin.