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

Misol.
561 soni uchun Ferma sinovini o‘tkazing.
Yechim
Asos sifatida 2 sonidag foydalanamiz.
2^561-1 = 1 mod 561
Son Ferma testidan o‘tdi, lekin bu tub son emas, nimagaki
.
Kvadrat ildiz sinovi
Modul arifmetikasida, , agar son bo‘lsa, u holda kvadrat ildiz faqat 1 ga teng bo‘ladi. Agar n murakkab bo‘lsa, u holda kvadrat ildiz.+1 yoki -1, ammo boshqa son bo‘lishi ham mumkin. Bu kvadrat ildiz tublikka tekshirish usuli deyiladi. E’tibor bersak, modul arifmetikasida -1 soni ni anglatadi.

Misol
Qaysi kvadrat ildiz 1 modn, agar 7ga teng bo‘lsa?
Misol 12.22
Qaysi kvadrat ildiz 1 mod n, agar n soni 8 ga teng bo‘lsa ?
Yechim
3 ta yechimni aniqlaydi: 1, 3, 5 i 7 (qaysiki natija –1). Biz yana ko‘rishimiz mumkinki
1² = 1 mod 8 (–1)² = 1 mod 8
3² = 1 mod 8 (–5)² = 1 mod 8
Misol 12.23
Qaysi son kvadrat ildizi agar n=17 bo‘lganda 1mod17 ga teng.
Yechim
Faqat ikkita yechim aniqlanadi, qo‘yilgan vazifaga javob beruvchilari: bu 1 i (–1).








Shuning uchun, 8 dan katta butun sonlarni tekshirish hojati yo‘q, chunki 9 = –8 mod 17
Rabin-Miller testi
Tub sonlarni aniqlaydigan Rabin Miller testi Ferma va Kvadrat ildiz testlarining kombinatsiyasidan iborat. Bu kuchli psevdotasodifiy sonlarni topishning elegant usulidir (kuchli ehtimollik bilan tub son). Bu testda biz toq son ni va 2 ning darajasini topish uchun sifatida ni yozib olamiz .

Fermat testida, a sosda, u quyida ko‘rsatilgandek yozilishi mumkin.
Fermaga asoslangan sonni tublikka tekshirish testi

Boshqacha qilib aytganda, biz bir qadamda an-1 (mod n) ni hisoblashning o‘rniga k + 1 bosqichda bajaramiz. Ushbu dasturning afzalligi nimada? Afzalligi shundaki, kvadrat ildiz sinovini har qadamda bajarish mumkin. Agar kvadrat ildiz shubhali natijalarni ko‘rsatsa, biz to‘xtatamiz va n kompozit sonni e’lon qilamiz. Har bir qadamda, Fermat testi va kvadrat ildiz sinovi, agar u qoniqarli bo‘lsa, qo‘shni barcha juftliklar bo‘yicha qoniqishini ta’minlaymiz.