|
Solovey-Shtassenning katta sonlarni tublikka sinash algoritmi
|
| bet | 2/3 | | Sana | 14.02.2024 | | Hajmi | 19,03 Kb. | | #156116 |
Bog'liq Kriptografiya 1 (Mustaqil ish)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 sonlar soni, 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. Ta'rif (Lejandr simvoli). Faraz qilaylik a – butun son va p≠ 2 tub son. U holda Lejandr simvoli quyidagicha aniqlanadi: – agar a p ga bo‘linsa : p= 0; – agar a p modul bo‘yicha kvadratik chegirma, ya'ni a p ga bo‘linmaydi va shunday butun x son mavjudki, x2 ≡ ( ) bo‘lsa, / = 1; – agar a p ga bo‘linmasa va a p modul bo‘yicha kvadratik chegirma bo‘lmasa, =−1. Ehtimollik testlari RSA yoki Rabin sxemasi kabi faktorizatsiya muammosiga asoslangan tizimlarda qo'llaniladi. Ammo, amalda, Solovay - Strassen testining ishonchliligi etarli emas, buning o'rniga Miller - Rabin testi qo'llaniladi. Bundan tashqari, birlashtirilgan algoritmlardan foydalaniladi, masalan, sinov bo'limi va MillerRabin testi, parametrlarni to'g'ri tanlash bilan siz har bir testni alohida qo'llashdan ko'ra yaxshiroq natijalarga erishishingiz mumkin. Algoritmni amalga oshirishda hisoblash murakkabligini kamaytirish uchun a raqamlari 0 < a < C < n oralig'idan tanlanadi, bu yerda C doimiy protsessor registriga joylashtirilgan tabiiy sonning maksimal qiymatiga teng. Solovey-Shtrassenning katta sonlarni tublikka sinash algoritmi Solovey - Strassen algoritmi k davr soni bo'yicha parametrlangan. Har bir turda tasodifiy ravishda a 1 bo'lsa, u holda n kompozit ekanligiga qaror qilinadi. Aks holda, taqqoslashning haqiqiyligi tekshiriladi \ textstyle a ^ {(n-1) / 2} \ equiv \ left ({a \ over n} \ right) \ pmod {n}. Agar u bajarilmasa, unda n kompozit ekanligi to'g'risida qaror qabul qilinadi. Agar bu taqqoslash to'g'ri bo'lsa, guvoh n sonining soddaligiga guvoh bo'ladi. Keyin yana bir tasodifiy a tanlanadi va protsedura takrorlanadi. K turda soddalikning n guvohlarini topgandan so'ng, n - 1 - 2 ^ {- k} ehtimollik bilan tub son degan xulosaga kelishdi.
Kirish:
• n> 2, sinab ko'rilgan toq tabiiy son;
• k, testning aniqligini aniqlaydigan parametr. Chiqish: Kompozit, n to'liq kompozitsiyani bildiradi;
• ehtimol bosh, n ning ehtimol bosh ekanligini anglatadi. for i = 1, 2, ..., k : a = tasodifiy butun son 2 dan n - 1 gacha, shu jumladan; agar NOD (a, n)> 1 bo'lsa, unda: n kompozit ekanligini va to'xtashini aniqlang. Agar a ^ {(n-1) / 2} \ not \ equiv \ left ({a \ over n} \ right) \ pmod {n} bo'lsa: n kompozit ekanligini va to'xtashini aniqlang.
• textstyle 1 - 2 ^ {- k} ehtimollik bilan n ning tub ekanligini aniqlang va to'xtating.
Solovey-Shtrassenning katta sonlarni tublikka sinash algoritmiga misol
14 p=19 ni Solovey-Shtrassen algoritmi bilan tublikka sinaymiz:
• k=1,
• 2 ≤ ≤ − 1 oraliqdan tasodifiy a=11 tanlaymiz.
• EKUB(a,r)= EKUB(11,19)=1
• Demak, ( −1)/2 ≡ /shartni bajarilishini tekshiramiz.
• = / =11/19= 1
• ( −1)/2 = 11(19−1)/219 = 1
• Taqqoslasak, demak, ( −1)/2 =( / ) k=2,
• 2 ≤ ≤ − 1 oraliqdan tasodifiy a=5 tanlaymiz.
• EKUB(a,r)= EKUB(5,19)=1
• Demak, ( −1)/2 ≡ /shartni bajarilishini tekshiramiz.
• = / =5/19= 1
• ( −1)/2 = 5(19−1)/219 = 1
• Taqqoslasak, demak, ( −1)/2 = /
• Bundan quyidagicha xulosaga kelish mumkin: 19 son 1-2 -2 ehtimollik bilan tub son bo‘ladi. 15 Solovey-Shtrassenning sonlarni tublikka tekshirish algoritmini dasturiy moduli public static boolean isPrimeAccordingToSoloveiShtrassen(int number, int accuracy){ //number > 2, нечётное натуральное число for (int i = 0; i < accuracy; i++){ int randomInt = randomIntInRange(2, number - 1); if (gcd(randomInt, number) > 1){ return false; } int checkNumberW = pow(randomInt, (number - 1) / 2, number); int jacobySignum = (jacobySign(randomInt, number) + number) % number; if (checkNumberW != jacobySignum){ return false; }} return true; }
|
| |
