|
I. Kirish II. Asosiy qism Ochiq kalitli kriptotizmlarda kalitlarni generatsiyalash usullari
|
| bet | 6/12 | | Sana | 05.12.2023 | | Hajmi | 385,21 Kb. | | #111359 |
Bog'liq xudo xoxlasa tushadi99%, 3-labarotoriya ishi Saralash usul va algoritmlarini tadqiq qilis, cmd buyruqlari, Incremental model nima, 1matematik, word sAM 1 savol, Документ Microsoft Word (4), Ma\'ruzalar (2), ЛАБОРАТОРНАЯ РАБОТА N1, Dasturlash 2, Ariza, Qalandarova Gulshoda, 1648631455, 1650692784, 1651669892 (2)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, x2 ≡ 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.
|
| |
