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

Primer 12.18
Faraz qilamiz, 200 bitga teng. Qanday sondagi razryad amalini bo‘lish algoritmida amalga oshirish kerak?
Resheniye
Bu algoritm bitli amalining murakkabligi—  . Bu shuni anglatadiki, algoritm bir qancha 2¹⁰⁰bit amallarni o‘tkazadi. Agar algoritm sekundiga 2³⁰ta amalni bajarish tezligiga ega bo‘lsa, u holda sinovni o‘tkazish uchun 2⁷⁰ soniya kerak bo‘ladi
Ehtimoliy algoritmlar
AKS algoritmigacha barcha tublikka tekshiruvchi samarali algoritmlar ehtimoliy bo‘lgan. Bu usullar AKS formal standart sifatida foydalanilishi mumkin edi.
Ehtimoliy algoritmlar natija to‘g‘riligiga kafolat bermaydi. Faqat biz bir qancha kichik ehtimollikdagi xatolikni olsak, algoritm to‘g‘ri natija ishlab chiqishiga kafolat beradi.
Algoritmning razryadli amallari murakkabligi polinomial qo‘yilishi mumkin, biz unchalik katta bo‘lmagan xato qilish itiyoziga ega bo‘lishimiz mumkin. Bu turkumdagi ehtimoliy algoritmlar quyidagi qoidalarga asoslanib tub yoki murakkab degan natijani beradi:
a. Agar tekshirilayotgan butun son haqiqatdan tub bo‘lsa, algoritm aniq tub sonni qaytaradi.
b. Agar tekshirilayotgan butun son haqiqaqtdan murakkab ob’ekt bo‘lsa, algoritm 1-e ehtimollik bilan murakkab ob’ektni qaytaradi, ammo e bilan tub sonni sonni qaytarishi ham mumkin. Agar algoritmni bir necha bor turli parametrlar bilan ishlasak yoki har xil usullardan foydalansak xato ehtimolligi yaxshilanishi mumkin. Agar algoritmni marta bajarsak, xato ehtimoli ga kamayishi mumkin.
Ferma testi
Biz muhokama qilayotgan birinchi ehtimollik usuli bu Fermatning tub sonlarni sinab ko‘rishidir.
Agar tub son bo‘lsa, u holda  tenglik o‘rinli.
E’tibor bering, agar n tub bo‘lsa, taqqoslash to‘g‘ri bo‘ladi. Lekin bu, taqqoslash to‘g‘ri bo‘lsa, n bu tub son bo‘ladi degani emas. Butun son tub yoki murakkab bo‘lishi mumkin . Fermat testi sifatida biz quyidagilarni aniqlashimiz mumkin:
Tub sonlar Fersa testini qanoatlantiradi. Murakkab sonlar ehtimollik bilan ferma testidan o‘tishi mumkin. Yekspopensialni hisoblao‘ kabi, Ferma testining razryadli amallari murakkabligi algoritm murakkabligiga teng. Agar nazorat bir nechta sonlarga bo‘lib yuborilsa, ehtimollik yanada yaxshi bo‘lishi mumkin.