|
Mersenne tub sonlarni tekshirish uchun testi
|
| bet | 4/12 | | Sana | 05.12.2023 | | Hajmi | 385,21 Kb. | | #111359 |
Mersenne tub sonlarni tekshirish uchun testi
Kiruvchi: Tub son p.
Topish: Mp = 2p − 1 ni hisoblang.
Ketma-ketlikni tuzing: {si} ketma-ketlikni quyidagi tartibda yaratish:
si = s2i−1 − 2, s0 = 4 bo'yicha, to p − 2 gacha i = p − 2 bo'lguncha davom ettirilsin.
Agar sp−2 ≡ 0 (mod Mp) bo'lsa, "Mp tub"ni qaytaring. Aks holda, "Mp composite"ni qaytaring.
Diqqat qiling, ketma-ketlik doimiy bo'lsa-da, si sonini hisoblash uchun kerak bo'lgan sanalar soni p o'lchamiga bog'liq. Bu, demak, 2-qadamda, s0 = 4 bilan boshlanadi va si = s2i−1 − 2 (mod Mp) p − 2 marta takrorlanadi.
To'g'ri bo'lish
sp−2 ≡ 0 (mod Mp) ⇐⇒ Mp tub bo'lishini isbotlash uchun, ω = 2 + √3 va ω = 2 − √3 ni aniqlab olishimiz kerak. Endi ω = ω2n + ω2n, bu yerda L0 = ω1 + ω1 = 4. Bundan tashqari, Ln+1 = ω2n+1 + ω2n+1 ni aniqlashimiz kerak. ωω = (2 + √3)(2 − √3) = 1 bo'lganidan, oxirgi tenglama ω2n+1 + ω2n+1 + 2ω2nω2n − 2 = (ω2n + ω2n+1)2 − 2 = L2n − 2 ga o'tkazilishi mumkin. Bu, Ln va si ning bir xil ketma-ketliklar bo'lishi kerakligini anglatadi. Endi, bu Ln ni isbatlash uchun uni theoremning har ikki tomonini ham ishlatishimiz mumkin.
"⇐": Mp = 2p − 1 bo'lgan qiymatlarga ega a + b√3 shaklidagi sonlar guruhi ko'rib chiqamiz (mod Mp). Bizga AKS algoritmning isbotidan sabab, (1 + √3)Mp ≡ 1 + √3 Mp (mod Mp) = 1+ √ √3 3 √3 Mp (mod Mp) = 1+(√3)3 Mp−1 2 (mod Mp). Kvadrat reciprocality qonuni orqali, 3 Mp−1 2 ≡ ±1 (mod Mp). Endi to'g'ri belgilash kerak bo'lgan alamatni aniqlashimiz. Mp va 3 mod 4 ga mos kelganda, kvadrat reciprocality qonuni bizga ayta, yoki Mp tub son yoki 3 tub son o'rniga bo'lishi mumkin. Bizda Mp ≡ 1 (mod 3), shuning uchun Mp tub son (mod 3) va shu sababli 3 Mp−1 2 ≡ −1 (mod Mp). Bu demak, (1+√3)Mp ≡ 1− √3 (mod Mp). Endi biz ildizni (1+ √3) bilan ko'paytirishimiz kerak, bu bizga (1+√3)Mp+1 ≡ −2 (mod Mp) ni beradi. Biz ham (1+√3)2 = (4+2√3) = 2ω deb yozishimiz mumkin, bu esa (1 + √3)Mp+1 ni (2ω) Mp+1 2 = 2 Mp+1 2 ω Mp+1 2 = 212 Mp−1 2 ω Mp+1 2 ≡ −2 (mod Mp) ga aylantiradi. Bizda 2 Mp−1 2 ≡ 1 (mod Mp) sababli, oxirgi tenglamani 12 2ω Mp+1 2 ≡ −2 (mod Mp) deb yozishimiz mumkin. 2 ning Mp ga nisbatan tub son bo'lishi sababli, bu oxirgi tenglama ω Mp+1 2 ≡ −Mp −1 ≡ −1 (mod Mp) ga o'tkaziladi. Biz bu tenglamani ω2p−1+1 2 = ω2p−1 = ω2p−2 ω2p−2 sifatida yozishimiz mumkin, bu esa Mp ga nisbatan −1 (mod Mp) ga teng bo'ladi. Hozir, biz bu tenglamani ω2p−2 bilan ko'paytirib olishimiz kerak, bu esa ω2p−2 + ω2p−2 ≡ sp−2 ≡ 0 (mod Mp) ga o'tadi.
"⇒": Mp sp−2 ni bo'ladigan qilish, ya'ni, CMp = ω2p−2 + ω2p−2. Biz bu tenglamani ω2p−2 bilan ko'paytirib olishimiz mumkin, shu bilan ω2p−1 = CMpω2p−2 − 1. Uning o'ng tarafini ko'paytirish uchun uni kvadratga olib yuboramiz, va bizga ω2p = (CMpω2p−2 − 1)2 ni olishimiz kerak. Mp tub son emas deb faraz qilamiz, bu esa, q < p Mp bo'lgan bo'lsa. Biz G sonlar guruhiga barcha q ni mod q bo'yicha invertib sonlar ekanligini ko'ramiz va ko'rishimiz kerak, chunki |G| ≤ q2 − 1 (0 ni invertib son sifatida o'z ichiga olmaydi).
|
| |
