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

Fermaning tub sonlari
Fermat asosiy sonlarni hosil qilish uchun formulani topishga harakat qildi. U hozirda Fermat formulasi deb ataladigan quyidagi formulani taklif qildi va F₀ (n = 0,1, ...) dan F₄ gacha bo‘lgan raqamlarni tekshirdi, ammo F₄ allaqachon tub son emasligi ma’lum bo‘ldi.

F₀ = 3
F₁ = 17
F₂ = 257
F₃ = 65537
. Tub son emas. Aslida, gacha bo‘lgan ko‘plab raqamlar aralash raqamlar ekanligi isbotlangan.
12.2. Sonlarni tublikka tekshirish
Agar biz Mersel va Ferma formulalari kabi algoritmlardan tub son hosil qilsak, olingan son tub son ekanligiga kafolat bera olmaymiz. Xo‘sh biz qagday qilib kriptografiyada katta tub sonlarni hosil qilishimiz mumkin? Biz faqat ixtiyoriy katta sonni olamiz va uni tub ekanligi aniqlovchi sinov o‘tkazamiz.
Juda katta tub sonlarni to‘g‘ri va effektiv hosil qiluvchi, uni tub yoki murakkab son ekanligini aniqlovchi ishonchli algoritmni hosil qilish doimo sonlar nazariyasida va kriptografiyada muammo bo‘lgan. Biroq, yaqinda o‘tkazilgan tadqiqotlar (biz ushbu bo‘limda muhokama qiladigan) juda istiqbolli ko‘rinadi.
Ushbu muammoni hal qiladigan algoritmlarni ikkita keng toifaga bo‘lish mumkin - deterministik algoritmlar va ehtimoliy algoritmlar. Quyida ikkala toifaning ba’zi vakillari.
A deterministik algoritm har doim to‘g‘ri javobni beradi.
Ehtimollar algoritmi ko‘p hollarda to‘g‘ri javobni beradi, ammo hamma holatlarda ham emas.
Garchi deterministik algoritm ideal bo‘lsada, u tegishli probabilistikga qaraganda kamroq samaralidir.
Determinicimk algoritmlar
Tublikka tekshiruvchi determinicimk algoritmlar,butun sonni qabul qiladi va chiqishda tub son yoki tub son yoki murakkab son degan xarakteristikani beradi. Bir qancha vaqtgacha barcha deterministik algoritmlar katta tub sonlarni topish uchun samarasiz bo‘lgan Qisqacha yangi ko‘rinishni namoyish qilar ekanmiz, ushbu algoritmlar ularni yanada istiqbolli qiladi.
.Bo‘lish nazariyasi algoritmi
Eng elementar deterministik tub sonlarni tekshirish bu bo‘lish bilan tekshirish. Biz barcha bo‘luvchi sonlar sifatida dan kichilaridan foydalanamiz. Agar bu sonlardan istalgani ga bo‘linsa, holbuki murakkab. 

Algoritm 12.1.
Algoritm 12.1da bo‘lish bo‘yicha tublikka sinash juda samarali va primitiv formada aks ettirgan. 
Algoritm faqatgina toq sonlarni tekshirsa yanada samarali ishlashi mumkin. U yana 2 va sonlar oralig‘idagi tub sonlar jadvalidan foydalanilsa yanada samarali bo‘lishi mumkin. 12.1 algoritmdagi arifmetik amallar soni  —  ga teng. Agar biz har bir arifmetik amal faqat bir bitdagi amallardan foydalanilishini qabul qilsak, u holda 12.1 algoritm razryadli amali murakkabligi ga teng, bu yerda n_b – bitlar soni  dagi. Katta tizimlarda, murakkablik ko‘rsatkichi,murakablik eksponensial O(2ⁿ) darajada baholanishi mumkin. Boshqa so‘z bilan aytganda bo‘lish sinovi agar n_b katta son bo‘lsa samarasiz hisoblanadi.