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

Initsializatsiya
Asosni tanlaymiz va T = a^m ni tanlaymiz, v kotorыy m = (n – 1) / 2^k.
a. Agar natija +1 yoki -1 ga teng bo‘lsa, ni kuchli psevdotubson deb e’lon qilamiz va jarayonni to‘xtatamiz. Biz sonini Ferma va kvadrat ildiz testidan o‘tdi deya aytishimiz mumkin.
b. Agar T soni boshqa natijaga teng bo‘lsa, biz sonin tub son yoki murakkab son ekanligiga ishonch hosil qila olmaymiz. Demak, jarayon keyingi qadamda davom etadi.
1 Qadam
T sonini kvadratga ko‘taramiz.
a. Agar natija +1 bo‘lsa, biz aniq bilamizki, Fermat testi o‘tgan, chunki T keyingi sinovlar uchun 1 bo‘lib qoladi. Ammo kvadrat ildiz sinovi muvaffaqiyatsiz tugadi. Ushbu bosqichda T 1 bo‘lganligi va oldingi bosqichda (avvalgi bosqichda to‘xtamaganimiz sababi) boshqacha ma’noga ega bo‘lganligi sababli n murakkab ob’ekt deb e’lon qilinadi va jarayon to‘xtaydi.
b. Agar natija (-1)ga teng bo‘lsa, chekli hisobda Ferma testidan o‘tishini bilamiz. Bilamizki, u kvadrat ildiz sinovidan ham o‘tadi, chunki bu qadamda natija (-1)ga teng bo‘ladi va keyinga qadamda 1 bo‘ladi. Biz ni kuchli psevdotasodifiy son deb e’lon qilamiz va jarayonni to‘xtatamiz.
c. Agar T yana qandaydir natijani bersa, tub son bo‘ladi deb ishonch hosil qila olmaymiz va jarayon keyingi qadamda davom etadi.
Qadamlar 2dan k–1 gacha
Bu qadam va qadamgacha 1- qadam kabi bo‘ladi.. Bu qadam muhim emas. Agar biz uni amalga oshirsak va natija olmasak, u bizga naf bermaydi. Agar bu qadam natijasi (-1) bo‘lsa, demak Ferma testidan o‘tadi, lekin oldingi qadam natijvsi sifatida olinmasa, kvadrat ildiz testidan o‘ta olmaydi, Agar jarayon qadam oxirigacha to‘xtamasa,biz ni murakkab son deb e’lon qilamiz.
Test Millera-Rabina trebuyet ot 0 do k–1..
Algoritm 12.2 Rabin Miller testi uchun psevdokodni ko‘rsatadi..

12.2. Millera-Rabin testi uchun psevdokod
Har safar Miller-Rabin testi har bir raqam uchun o‘tkazilganda, "unchalik katta bo‘lmagan" natijani olish ehtimoli 1/4 ni tashkil qiladi. Agar sinovdan o‘tgan bo‘lsa, testning tub bo‘lmaslik bermaslik ehtimoli (1/4) ..