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

Misol 12.11
O’zaro tub elementlar nimalardan iborat?
Yechim
. Elementlar – bular 1, 3, 5, 9, 11 i 13.
Qiziq fakt: agar n > 2 bo‘lsa, — juft bo‘ladi.
Fermaning kichik teoremasi
Fermatning kichik teoremasi sonlar nazariyasi va kriptografiyasida juda muhim rol o‘ynaydi. Quyida teoremaning ikkita versiyasini beramiz.

1. 
   versiya
   

Birinchi versiyada, agar soni tub bo‘lsa va soni soniga bo‘linmaydigan butun son bo‘lsa, u holda o‘rinli.
Ikkinchi versiya
Ikkinchi versiyada a-da cheklov sharti keltirilgan. Uning ta’kidlashicha, agar p tub son bo‘lsa va a butun son bo‘lsa, u holda?   .
Ilova
Keyinchalik ushbu ma’ruzada ushbu teoremaning qo‘llanilishini ko‘rib chiqsak ham, teorema ba’zi muammolarni hal qilishda juda foydali.
Eksponentlash. Fermatitning kichik teoremasi eksponentatsiyaga tezda yechim topish uchun ba’zida foydalidir. Buni quyidagi misollar ko‘rsatib turibdi.
Misol 12.12
6¹⁰ mod 11 qiymtini toping
Yechim
Biz olamiz. Bu Fermataning kichik teoremasining birinchi versiyasi., bu yerda p = 11.
Multiplikativ teskarilash. Agar modul tub son bo‘lsa,  Fermat teoremasi bir nechta multiplikativ inversiyalar uchun juda qiziqarli dasturni topdi, agar tub son bo‘lsa va soni soniga bo‘linmaydigan butun son bo‘lsa, u holda togda a^-1mod p = a^p-2 mod p o‘rinli. Agar tenglikning ikkala tomonini ga ko‘paytirsak va Fermatning kichik teoremasi--ning birinchi versiyasidan foydalansak, buni isbotlash mumkin.

Ushbu ifoda kengaytirilgan Yevklid algoritmidan foydalanmasdan, sonning multiplikativ teskarisini topish imkonini beradi.
Misol 12.14
Butun sonning modul bo‘yicha teskari qiymatini kengaytirilgan Yevklid algoritmidan foydalanmasdan topishimiz mumkin:
a. 8^-1 mod 17 = 8^17-2 mod 17 = 8¹⁵ mod 17 = 15 mod 17
b. 5 ^–1 mod 23 = 5^23-2 mod 23 = 5²¹ mod 23 = 14 mod 23
c. 60¹⁰¹ mod 101 = 60^101-2 mod 101 = 60⁹⁹ mod 101 = 32 mod 101
d. 22 ^-1 mod 211 = 22 ^211-2 moda 211 = 22²⁰⁹ mod 211 = 48 mod 211
Eyler teoremasi
Eyler teoremasini Fermaning kichik teoremasini umumlashtirish sifatida ko‘rsatish mumkin. Ferma teoremasida modul bu tub son, Eyler teoremasida modul bu butun son. Ushbu teoremaning ikkita versiyasini taqdim etamiz