|
Sonlarni tublikka tekshirishning ehtimollik algoritmlari
|
| bet | 5/12 | | Sana | 05.12.2023 | | Hajmi | 385,21 Kb. | | #111359 |
Sonlarni tublikka tekshirishning ehtimollik algoritmlari
Fermaning 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 an−1 ≡ 1 (mod n) tenglik o‘rinli bo‘ladi,
bunda a ixtiyoriy va n a ga karrali emas. an−1 ≡ 1 (mod n) tenglikni bajarilishi berilgan n sonning tubligini aniqlovchi zaruriy va yetarli shartdir. Ya'ni agar biror bir
a uchun an-1 ≠ 1 (mod n) 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
an-1≡ 1 (mod n) taqqoslama bajarilsa, u holda n son a asos bo‘yicha psevdotub deyiladi. Ammo n son murakkab bo‘lganda, shunday a topiladiki, an−1 ≠1 (mod n) 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 (mod341) taqqoslama bajariladi. Ammo 3 asos bo‘yicha hisoblansa
3340≡ 56 (mod341) ≠ 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 qancha a soni tanlanadi. Shartni qanoatlantiruvchi a soni qancha ko‘p bo‘lsa, nsonni 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 yerda n - tekshiriladigan raqam. Odatda turli xil a bilan bir nechta tekshiruvlar mavjud.
2.2 Solovey-Shtassenning katta sonlarni tublikka sinash algoritmi
Solovey - Strassen testi 1970-yillarda Robert Martin Solovey tomonidan Volker Strassen bilan birgalikda kashf etilgan soddalikning ehtimollik sinovidir. Sinov har doim ham tub
sonning tub ekanligini to'g'ri aniqlaydi, ammo kompozit sonlar uchun u biron bir ehtimollik
bilan noto'g'ri javob berishi mumkin. Sinovning asosiy afzalligi shundaki, u Ferma testidan
farqli o'laroq, u Karmikel sonlarini aralash sonlar sifatida tan oladi. XVII asrda Ferma
keyinchalik Fermaning kichik teoremasi deb nomlangan bayonotni isbotladi va bu
Fermaning soddaligi uchun sinovining asosi bo'lib xizmat qildi. Agar n toq kompozitsion
son bo'lsa, unda taqqoslashni qondiradigan butun sonlarsoni, p va p dan kichik bo'lgan
nusxalar ( −1)/2 ≡ / qondiradi va p/2 dan oshmaydi. Berilgan p uchun ushbu tekshiruv juda
ko'p hisoblashni talab qilmaydi, ammo buning aksi to'g'ri emas. Shunday qilib, Karmayel
raqamlari mavjud, ular birlashtirilgan bo'lib, ular uchun Fermaning kichik teoremasida
keltirilgan bayonot berilgan son bilan ko'chirilgan barcha butun sonlar uchun amal qiladi.
1994 yilda bunday sonlar cheksiz ko'p ekanligi ko'rsatildi. Ferma testining aniqlangan
kamchiliklari bilan bog'liq holda, ehtimollik testlarining ishonchliligini oshirish vazifasi dolzarb bo'lib qoldi. Leman birinchi bo'lib Karmayelning raqamlarini kompozit sifatida
yo'q qiladigan testni taklif qildi. Bu kamchilik Solovay - Strassen va Miller - Rabin testlarida Fermaning kichik teoremasiga qaraganda kuchliroq tark etish mezonlari tufayli yo'q. Bir-biridan mustaqil ravishda 1976 yilda D. Lexmer va 1977 yilda R. Solovey F. Strassen bilan
birgalikda Karmikel sonlarining analogi mavjud emasligini isbotladilar, ular birlashgan va shu bilan birga Eyler psevdosimplesidir.Shunga asoslanib, soddalik uchun Nightingale -
Strassen testi taklif qilindi, 1977 yilda nashr etildi va 1978 yilda to'ldirildi.Test har doim tub sonining tubligini to‘g‘ri aniqlaydi, ammo murakkab sonlar uchun ma'lum ehtimollik bilan noto‘g‘ri javob terishi mumkin. Testning asosiy afzalligi shundaki, u Ferma testidan farqli holda Karmaykl sonlarini murakkab son sifatida aniqlaydi. Ushbu testda Eyler kriteriysidan
foydalaniladi.Ma'lumki, Eyler kriteriysiga ko‘ra, agar r bilan eng katta umumiy bo‘luvchiga ega bo‘lmagan barcha tub sonning guvohlari a uchun ( −1)/2≡ / shart qanoatlantirilsa, p toq
soni tub son bo‘ladi. Ya'ni, mazkur algoritmda tub sonlar darajalari jadvalining (p-1)/2
qatorida r bilan o‘zaro tub bo‘lgan “tublik guvohlari” a ga tegishli ustunda hosil bo‘ladigan
1 va -1 elementlariga e'tibor qaratiladi.
|
| |
