I. Kirish II. Asosiy qism Ochiq kalitli kriptotizmlarda kalitlarni generatsiyalash usullari

Download 385,21 Kb.
bet	6/12
Sana	05.12.2023
Hajmi	385,21 Kb.
	#111359

1 2 3 4 5 6 7 8 9 ... 12

Solovey-Shtrassenning katta sonlarni tublikka sinash algoritmi

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 : (a/p)= 0;
– agar a p modul bo‘yicha kvadratik chegirma, ya'ni a p ga bo‘linmaydi va shunday
butun x son mavjudki, x² ≡ a(mod p) bo‘lsa, a/p = 1;
– agar a p ga bo‘linmasa va a p modul bo‘yicha kvadratik chegirma bo‘lmasa, a/p=−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 Rabin-Miller testi qo'llaniladi. Bundan tashqari, birlashtirilgan algoritmlardan foydalaniladi, masalan, sinov bo'limi va Rabin-Miller 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 ^ {(n1) / 2} \
equiv \ left ({a \ over n} \ right) \ pmod {n}.
Agar u bajarilmasa, unda n kompozit ekanligi to'g'risida qaror qabul qilinadi.Agar bu taqqos-
lash 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.

Download 385,21 Kb.

1 2 3 4 5 6 7 8 9 ... 12

Download 385,21 Kb.