|
O’zbekiston Respublikasi axborot texnologiyalari va kommunikatsiyalarini rivojlantirish vazirligi Muhammad Al-Xorazmiy nomidagi Toshkent axborot texnologiyalar universiteti kiberxavfsizlik fakulteti
|
| bet | 1/3 | | Sana | 14.02.2024 | | Hajmi | 19,03 Kb. | | #156116 |
Bog'liq Kriptografiya 1 (Mustaqil ish)
O’zbekiston Respublikasi axborot texnologiyalari va kommunikatsiyalarini rivojlantirish vazirligi
Muhammad Al-Xorazmiy nomidagi Toshkent axborot texnologiyalar universiteti kiberxavfsizlik fakulteti.
Kiriptografiya 1 fanidan
Mustaqil ish
Bajardi: Ismoilov Axliddin.
Tekshirdi: Jabbarov Nuriddin
Toshkent-2024.
Mustaqil ish.
Mavzu: Sonlarni tublikka tekshirish algoritmlari.
Reja:
Fermaning katta sonlarni tublikka tekshirish testi.
2. Solovey-Shtrassenning katta sonlarni tublikka tekshirish testi.
3. Rabin Millerning katta sonlarni tublikka tekshirish testi.
4. Lucas tublikka tekshirish testi.
5. Frobenius kvadratik tublikka tekshirish testi.
1.Fermaing katta sonlarni tublikka sinash algoritmi.
Tub sonlarni generatsiya qilish oshkora kalitli kriptotizimlarni loyihalashda asosiy bosqichlardan biri hisoblanadi. Chunki, ular asosida modul arifmetikasining hal qiluvchi elementi, ya'ni moduli shakllantiriladi. Kriptotizimning bardoshliligi esa tanlanadigan modulning xossalariga bevosita bog‘liqdir.Tub sonlarni generatsiya qilishda qo‘llaniladigan barcha algoritmlar ma'lum ehtimollik bilan tub sonni hosil qiladi. Bunday tublikka sinash algoritmlariga - Fermaning katta sonlarni tublikka sinash algoritmi, SoloveyShtrassenning katta sonlarni tublikka sinash algoritmi, Lemanning katta sonlarni tublikka sinash algoritmi, Rabin-Millerning katta sonlarni tublikka sinash algoritmi va boshqalar kiradi. Sinash algoritmlari qanchalik ko‘p "tublikka guvohlar"ni ko‘rsatsalar, sinalayotgan n sonining tub bo‘lish ehtimolligi shunchalik katta bo‘ladi. Biz muhokama qiladigan birinchi ehtimollik usuli bu Fermaning oddiy sonlarni sinashidir. Fermaning sonlar nazariyasidagi soddaligi testi–bu Fermatning kichik teoremasi asosida natural son n ning soddaligini sinashdir. Agar n- tub son bo‘lsa, u holda “Fermaning kichik teoremasi ” ga ko‘ra −1 ≡ 1 ( ) tenglik o‘rinli bo‘ladi, bunda a ixtiyoriy va n a ga karrali emas. −1 ≡ 1 ( ) tenglikni bajarilishi berilgan n sonning tubligini aniqlovchi zaruriy va yetarli shartdir. Ya'ni agar biror bir a uchun −1 ≠ 1 ( ) bo‘lsa, u holda p murakkab son bo‘ladi, aks holda esa biror aniq narsa aytish qiyin, ammo sonning tublik ehtimoli ortadi. Agar murakkab son n uchun −1 ≡ 1 ( ) taqqoslama bajarilsa, u holda n son a asos bo‘yicha psevdotub deyiladi. Ammo p son murakkab bo‘lganda, shunday a topiladiki, −1 ≠1 ( ) taqqoslama bajarilmaydi, bunday a son n sonning murakkabligiga guvoh deyiladi, bunda taqqoslama bajarilgan avvalgi a son esa, n sonning tubligiga “soxta guvoh” deyiladi. Murakkab butun son n=341(=11∙31) son 2 asos bo‘yicha psevdotub deyiladi, chunki 2340 ≡ 1 ( 341) taqqoslama bajariladi. Ammo 3 asos bo‘yicha hisoblansa 3340 ≡ 56 ( 341) ≠ 1 . Demak, a=2 tublikka “soxta tublik guvohi” va a=3 esa murakkablik guvohi bo‘ladi. Shuning uchun, sonni Ferma teoremasi bo‘yicha tublikka sinaganda bir 11 qancha a soni tanlanadi. Shartni qanoatlantiruvchi a soni qancha ko‘p bo‘lsa, n sonni tub bo‘lish ehtimoli shuncha katta bo‘ladi. Lekin shunday murakkab n sonlar borki, ular uchun taqqoslama n bilan tub bo‘lgan ixtiyoriy a sonda bajariladi. Bunday sonlar Karmaykl sonlari deyiladi. Karmaykl sonlari to‘plami cheksiz to‘plam bo‘lib, ularning eng kichigi – n=561=3∙11∙17. Shunga qaramay Ferma testi murakkab sonlarni aniqlashda samarali hisoblanadi. Tez eksponentlanish moduli uchun algoritmlardan foydalanilganda, bir a uchun Ferma testining ishlash vaqti O (log2n × log log n × log log log n) deb hisoblanadi, bu erda n - tekshiriladigan raqam. Odatda turli xil a bilan bir nechta tekshiruvlar mavjud.
|
|
Bosh sahifa
Aloqalar
Bosh sahifa
O’zbekiston Respublikasi axborot texnologiyalari va kommunikatsiyalarini rivojlantirish vazirligi Muhammad Al-Xorazmiy nomidagi Toshkent axborot texnologiyalar universiteti kiberxavfsizlik fakulteti
|
