1-ma’ruza Mavzu: rsa ochiq kalitli shifrlash algoritmi Reja
Download 0.53 Mb.
|
1-maruza
- Bu sahifa navigatsiya:
- Qadamlar 2dan k–1 gacha
- Test Millera-Rabina trebuyet ot 0 do k–1..
Initsializatsiya
Asosni tanlaymiz va T = am ni tanlaymiz, v kotorыy m = (n – 1) / 2k. 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) .. Download 0.53 Mb. Do'stlaringiz bilan baham: |
Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling
ma'muriyatiga murojaat qiling