|
Rabin Millerning katta sonlarni tublikka sinash algoritmi
|
| bet | 3/3 | | Sana | 14.02.2024 | | Hajmi | 19,03 Kb. | | #156116 |
Bog'liq Kriptografiya 1 (Mustaqil ish)Rabin Millerning katta sonlarni tublikka sinash algoritmi.
Rabin Miller- testi ehtimoliy polinom soddaligi testi eyiladi. Miller - Rabin testi, Ferma testi va Solovey Shtrassen testi bilan bir qatorda berilgan sonning kompozit ekanligini samarali aniqlashi mumkin. Biroq, bu raqamning asosiy ekanligini qat'iy isbotlash uchun ishlatilishi mumkin emas. Shunga qaramay, Miller-Rabin testi ko'pincha katta tasodifiy sonlarni olish uchun kriptografiyada qo'llaniladi. Rabin-Miller algoritmi - bu Gari Miller tomonidan 1976 yilda ishlab chiqilgan Miller algoritmining modifikatsiyasi hisoblanadi. Millerning algoritmi deterministik, ammo uning to'g'riligi isbotlanmagan kengaytirilgan Riman gipotezasiga asoslangan . Maykl Rabin uni 1980 yilda o'zgartirgan . Miller - Rabin algoritmi gipotezaning asosliligiga bog'liq emas, lekin bu ehtimollikdir. Ko'plab shifrlash algoritmlarining kriptografik kuchi maxfiy kalitlarga asoslanganligi sababli, ularni yaratish uchun asosiy raqamlar kerak (masalan, RSA shifrining ishlashi shunday), bunday tugmachalarni yaratishda katta raqamlarni tezda oddiylikda tekshirib ko'rish kerak. Miller-Rabin testi va Solovey-Shtrassen testi kabi probabilistik soddalik testlari deterministik testlarga nisbatan katta samaradorlik va ifoda qulayligini ko'rsatadi. Miller-Rabin algoritmi jarayonni qisqa vaqt ichida amalga oshirishga imkon beradi va shu bilan birga raqamning aslida kompozit bo'lish ehtimoli juda kichik bo’ladi. Fermat va Solovey Strassen testlari singari, Miller-Rabin testi ham asosiy sonlar uchun tenglik qatoriga tayanadi. Agar hech bo'lmaganda bunday tenglik qondirilmasa, bu raqamning birlashtirilganligini tasdiqlaydi . Rabin – Millerning katta sonlarni tublikka sinash testi hozirgi kunda nosimmetrik kriptotizimlarda modul hosil qilishda keng qo‘llaniladi. Bu algoritm kuchli psevdotub sonlarni sinash algoritmi sifatida tan olingan. U n -1 ni, ya'ni modulni bitta kamaytirilgan qiymatini 2s*r ko‘rinishda ifodalashga asoslangan. Bunda s ─ n -1 ni ikkiga bo‘linishlar soni, r – toq son. “n - soni tubmi?” degan savolga, “tub” yoki “murakkab” degan javob olishga qaratilgan bo‘ladi.
• n -1 = 2s*r ko‘rinishda yozib olinadi, bunda r - toq son;
• ≤ ≤ − 1 shartni qanoatlantiruvchi a son tasodifiy
• Agar (u=1 yoki u=n -1) bo‘lsa, u holda keyingi iteratsiyaga o‘tish.
• 2 ≡ −1 ( ) hisoblanadi;
XULOSA.
“Sonlarni tublikka tekshirish algoritmini dasturiy modulini ishlab chiqish” ushbu loyiha ishida tub sonlarni tarix, tub sonlarni generatsiya qiluvchi va ularni tublikka tekshiruvchi bir qancha algoritmlarni o’rganib chiqdik.Tub sonlarni generatsiya qilishda qo‘llaniladigan barcha algoritmlar ma'lum ehtimollik bilan tub sonni hosil qiladi. Bunday tublikka sinash algoritmlariga - Fermaning katta sonlarni tublikka tekshirish algoritmi, Solovey-Shtrassenning katta sonlarni tublikka tekshirish algoritmi, Lemanning katta sonlarni tublikka tekshirish algoritmi, Rabin-Millerning katta sonlarni tublikka tekshirish algoritmi va boshqalar kiradi. Tekshirish algoritmlari qanchalik ko‘p "tublikka guvohlar"ni ko‘rsatsalar, tekshirilayotgan n sonining tub bo‘lish ehtimolligi shunchalik katta bo‘ladi.
Foydalanilgan adabiyotlar:
Kriptografiya kitoblari.
Internet saytlari:
https://www.wikipedia.org
https://www.library.uz
https://www.hozir.org
Ma’ruza matnlari.
|
| |
