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

Yechish
2 asosdan foydalanib, , ni olamiz, bu yerda m = 35, k = 4 i a = 2 ni anglatadi.

Primer 12.26
Misol.
Biz bilamizki, 27 tub son emas. Millera-Rabin testini sinab ko‘ramiz.
Yechim
2 ga teng asos, , holbuki  , m = 13, k = 1 i a = 2 ni anglatadi. Bu holda  k – 1 = 0 va biz faqat initalizatsiya qadamini bajarishimiz kerakholos:
T = 2¹³ mod 27 = 11 mod 27. Lekin algoritm sifatida biror qadam ham ish bajarmadi, yechimni ishlab chiqamiz “murakkab son”.
Tavsiya etilgan sonlarni tublikka tekshirish testlari
Bugungi kunda eng mashhur tublik sinovlaridan biri bu bo‘linish nazariyasi va Miller-Rabin testining kombinatsiyasi. Quyidagi amallarni bajarish tavsiya etiladi:

1. 
   Tub bo‘lmagan sonni tanlang, chunki hamma juft butun sonlar aniq murakkab ob’ektlardir.
   
2. 
   1. 2. 3, 5, 7, 11, 13 kabi taniqli oddiy sonlarga bo‘linish nazariyasining ba’zi bir arzimas sinovlarini o‘tkazing: aniq aralash ob’ekt bilan ishlamasligingizga ishonch hosil qilish uchun. Agar ushbu barcha sinovlarda ular bo‘linmasa, keyingi bosqichga o‘ting. Agar tanlangan raqam ushbu testlarning kamida bittasida muvaffaqiyatsiz bo‘lsa, bir qadam orqaga qayting va boshqa toq raqamni tanlang.
   
3. 
   Sinov uchun asoslar to‘plamini tanlang. Ko‘p sonli bazalarga afzallik beriladi.
   
4. 
   Har bir asosda Miller-Rabin testini o‘tkazing. Agar ulardan biri bajarilmasa, bir qadam orqaga qayting va boshqa toq raqamni tanlang. Agar testlar har qanday sabablarga ko‘ra o‘tgan bo‘lsa, unda bu sonni kuchli soxta premer raqam deb e’lon qiling.