|
I. Kirish II. Asosiy qism Ochiq kalitli kriptotizmlarda kalitlarni generatsiyalash usullari
|
| bet | 3/12 | | Sana | 05.12.2023 | | Hajmi | 385,21 Kb. | | #111359 |
Pocklington testi
Soni sanoatni tekshirishning boshqa usuli "Pocklington(-Lehmer) sanoat tekshiruvi" [7] deb ataladi. Ismidan ham ko'rsatilishi kabi, testni Henry Cabourn Pocklington va Derrick Henry Lehmer tuzishdi. Ushbu test sanoat sonini tekshirish uchun ishlatiladi, ammo AKS testidan farqli ravishda natija beradi. AKS testi "sanoat" yoki "ko'p"ni chiqaradi, lekin Pocklington testi sanoat sertifikatini qaytaradi: kiritilgan sonning sanoat yoki emasligini isbotlovchi dalilni. Ya'ni, agar kiritilgan son sanoat bo'lmasa, chiqish "tugilmagan" bosqichni qaytaradi. Algoritm quyidagicha:
1.5.1 Algoritm
Kirish: butun son n > 1. 1 < a < n va q musbat butun sonlari bo'lsin.
Agar √n - 1 dan katta bo'lmagan q|n - 1 bo'lgan tub son q mavjud bo'lmasa, "aniq emas (bosqich 1)" ni qaytarish.
Tekshirish: a^(n-1) ≡ 1 (mod n) teng bo'lsa, "ko'p emas (bosqich 2: a)" ni qaytarish.
Tekshirish: gcd{a^(n-1)q-1, n} = 1 bo'lsa, "tub (a)" ni qaytarish. Aks holda, boshqa q uchun algoritmani qaytarish.
1.5.2 To'g'rilik
Ma'lum bo'lishicha n sanoat soni. Bu n sanoat bo'lganidan n kam bo'lgan tub bo'lagi p ≤ √n ni o'z ichiga oladi. Qandaydir q> √n deb tanlaganidan, biz bilmizki, q > p - 1 va shu sababli gcd{q, p - 1} = 1, ya'ni, q ning modulli ko'paytiruvchi inversiyasi x mod p - 1: xq ≡ 1 (mod p - 1) ga ega. Hozir, agar a ni topib, a^(n-1) ≡ 1 (mod n) teng bo'lganini sanabmiz. (E'tibor bering, agar a ni topib, a^(n-1) 6≡ 1 (mod n), bu n sanoat bo'lganini bildiruvchi Fermat testi shahidi bo'ladi.) Chunki p n ga bo'linadi, bizda a^(n-1) ≡ 1 (mod n) ≡ 1 (mod p) bo'lgani uchun, birinchi qismni quyidagi ko'rinishda yozishimiz mumkin: a^(n-1) ≡ (a^(n-1))^x ≡ a^(x(n-1)) ≡ a^(xq n-1) ≡ (a^(xq))^(n-1)q. Biz shu bilan ham bilamizki, Fermatning kichik qonuni va xq ≡ 1 (mod p - 1) dan foydalanib a^(xq) ni oddiy ko'rinishda yozishimiz mumkin. xq c(p - 1) + 1 ko'rinishida bo'lib, shuning uchun a^(xq) = a^(c(p-1)+1) = (a^(p-1))^ca^(1) ≡ 1/ca ≡ a (mod p). Bu degani, bizga quyidagi tenglikni hosil qilish imkoniyatiga ega bo'lamiz: (a^(xq))^(n-1)q ≡ a^(n-1)q (mod p), shuning uchun a^(n-1)q ≡ 1 (mod p). Endi biz bilmizki, p n ga bo'linadi va p a^(n-1)q - 1 bo'lib, shuning uchun 3-bosqichdagi eng katta umumiy bo'luvchi 1 emas. Bu shoh saqlangan.
1.5.3 Murakkablik
Eng yomon holatda, biz n - 1 ni bo'lgan har bir q uchun algoritmni loopdan o'tkazishimiz kerak. Bu degani, n - 1 ni hisoblashni talab qiladi, bu amalning murakkabi O(exp(C(ln n)^(1/3)(ln ln n)^(2/3))) ga teng. 2-bosqichdagi hisoblash O(log(n)^3) darajasi bilan bajariladi. 3-bosqichdagi GCDni hisoblash O(log(n)^3 * log(n)^2) = O(log(n)^5) ga teng. Ushbu algoritm murakkabi shu formula bo'yicha bo'ladi: O((exp(C(ln n)^(1/3)(ln ln n)^(2/3)))(log(n)^5 + ε)).
1.5.4 Tub son yaratish
Agar kiritilgan son n0 tub son ekanligini bilganimizda, uni yana bir marta algoritmga qo'shishimiz mumkin, bu safar q1 sifatida. Bu degani, biz tub sonning sertifikatini (u, bog'liq q0) qo'llash orqali katta tub sonlarni yaratishimiz mumkin. Yangi kirish soni n1 ning ba'zi chegaralariga ega. Chunki u q1 va q > √n, shu sababli n < q2 + 2q + 1. Misol: 3 tub son ekanligini bilamiz. Bu degani, uni q0 sifatida ishlatish orqali katta tub sonlarni topishda 3 ni qo'llaymiz, shuning uchun n0 < q0^2 + 2q0 + 1 = 16. Qandaydir n0, q0|n0 - 1 shartiga javob bermadi.
|
| |
