Tarkib

• Qadamlar
• 3dan 1 -qism: Oddiylik testlari
• 3dan 2 qism: Oddiylik testlari qanday ishlaydi
• 3dan 3 qism: Xitoy qoldiqlari teoremasidan foydalanish
• Maslahatlar
• Sizga nima kerak

Bosh sonlar faqat o'zlariga va 1 ga bo'linadigan sonlardir. Boshqa barcha sonlar kompozit sonlar deyiladi. Raqamning boshlang'ich ekanligini aniqlashning ko'plab usullari mavjud va ularning har biri o'zining afzalliklari va kamchiliklariga ega. Bir tomondan, ba'zi usullar juda aniq, lekin agar siz katta sonlar bilan ishlasangiz, ular ancha murakkab. Boshqa tomondan, juda tez yo'llar bor, lekin ular noto'g'ri natijalarga olib kelishi mumkin. Tegishli usulni tanlash siz ishlayotgan raqamlarning qanchalik katta bo'lishiga bog'liq.

Qadamlar

3dan 1 -qism: Oddiylik testlari

Eslatma: barcha formulalarda n tekshiriladigan raqamni bildiradi.

1. 1 Bo'linuvchilarni ro'yxatga olish. Ajratish kifoya n 2 dan yaxlitlangan qiymatgacha bo'lgan barcha oddiy sonlarga (${ Displaystyle { sqrt {n}}}$).
2. 2 Fermatning kichik teoremasi. Ogohlantirish: ba'zida test noto'g'ri raqamlarni aniqlaydi, hatto a ning barcha qiymatlari uchun ham.
   • Keling, butun sonni tanlaymiz a2 ≤ a ≤ n - 1.
   • Agar a (mod n) = a (mod n) bo'lsa, bu son, ehtimol, bosh. Agar tenglik qondirilmasa, n raqami birlashtirilgan.
   • Bir nechta qiymatlar uchun berilgan tenglikni tekshiring ahaqiqatan ham sinovdan o'tkazilayotgan sonning yuqori bo'lish ehtimolini oshirish.
3. 3 Miller-Rabin testi. Ogohlantirish: ba'zida, kamdan -kam hollarda, a -ning bir nechta qiymatlari uchun, test noto'g'ri raqamlarni boshlang'ich sifatida aniqlaydi.
   • S va d miqdorlarni toping ${ Displaystyle n-1 = 2 ^ {s} * d}$.
   • Butun sonni tanlang a 2 ≤ a ≤ n - 1 oralig'ida.
   • Agar a = +1 (mod n) yoki -1 (mod n) bo'lsa, unda n, ehtimol, eng yaxshi. Bunday holda, test natijalariga o'ting. Agar tenglik mos kelmasa, keyingi bosqichga o'ting.
   • Javobingizni kvadratga qo'ying (${ Displaystyle a ^ {2d}}$). Agar siz -1 (mod n) olsangiz, unda n, ehtimol, asosiy sondir. Bunday holda, test natijalariga o'ting. Agar tenglik bajarilmasa, takrorlang (${ Displaystyle a ^ {4d}}$ va boshqalar) qadar ${ Displaystyle a ^ {2 ^ {s-1} d}}$.
   • Agar kvadratchadan keyin bir necha qadam boshqa raqam bo'lsa ${ Displaystyle pm 1}$ (mod n), sizda +1 (mod n) bor, shuning uchun n - kompozit son. Agar ${ Displaystyle a ^ {2 ^ {s-1} d} neq pm 1}$ (mod n), keyin n asosiy emas.
   • Sinov natijasi: agar n testdan o'tgan bo'lsa, uni boshqa qiymatlar uchun takrorlang aishonchini oshirish uchun.

3dan 2 qism: Oddiylik testlari qanday ishlaydi

1. 1 Bo'linuvchilarni ro'yxatga olish. Ta'rif bo'yicha, raqam n faqat 2 va boshqa tamsayılarga bo'linmasa 1 va o'zidan tashqari oddiy. Yuqoridagi formula keraksiz qadamlarni olib tashlash va vaqtni tejash imkonini beradi: masalan, raqam 3 ga bo'linishini tekshirgandan so'ng, uning 9 ga bo'linishini tekshirishning hojati yo'q.
   • Floor (x) funktsiyasi x ni x dan kichik yoki teng bo'lgan eng yaqin tamsayunga aylantiradi.
2. 2 Modulli arifmetika haqida bilib oling. "X mod y" operatsiyasi (mod - lotincha "modulo" so'zining qisqartmasi, ya'ni "modul") "x ni y ga bo'lgin va qolganini top" degan ma'noni anglatadi. Boshqacha aytganda, modulli arifmetikada, ma'lum bir qiymatga yetganda, deyiladi modul, raqamlar yana nolga "buriladi". Masalan, soat 12 -modul bilan sanaladi: u 10, 11 va 12 soatni ko'rsatadi va keyin 1 ga qaytadi.
   • Ko'p kalkulyatorlarda mod kaliti mavjud. Ushbu bo'limning oxirida sizga bu funktsiyani katta sonlar uchun qanday hisoblash mumkinligi ko'rsatilgan.
3. 3 Fermatning kichik teoremasining tuzoqlari haqida bilib oling. Sinov shartlari bajarilmagan barcha raqamlar birlashtirilgan, qolgan raqamlar esa faqat ehtimol oddiy. Agar noto'g'ri natijalarni oldini olmoqchi bo'lsangiz, qidiring n "Karmaykel raqamlari" (bu testni bajaradigan kompozit raqamlar) va "Fermat soxta vaqt raqamlari" ro'yxatida (bu raqamlar faqat ba'zi qiymatlar uchun test shartlariga javob beradi) a).
4. 4 Agar qulay bo'lsa, Miller-Rabin testidan foydalaning. Garchi bu usul qo'lda hisoblash uchun ancha murakkab bo'lsa -da, u ko'pincha kompyuter dasturlarida qo'llaniladi. Bu qabul qilinadigan tezlikni va Fermat usulidan ko'ra kamroq xatolarni ta'minlaydi. Agar hisoblar ¼ dan ortiq qiymatlar uchun bajarilsa, kompozit raqam asosiy raqam sifatida qabul qilinmaydi a... Agar siz tasodifan turli qiymatlarni tanlasangiz a va ularning hammasi uchun test ijobiy natija beradi, bunga ishonchimiz komil bo'lishi mumkin n asosiy raqam hisoblanadi.
5. 5 Katta raqamlar uchun modulli arifmetikadan foydalaning. Agar sizda qulay hisob kalkulyatori bo'lmasa yoki kalkulyator bunday katta sonlarni qayta ishlash uchun mo'ljallanmagan bo'lsa, hisob -kitoblarni osonlashtirish uchun quvvat xususiyatlari va modulli arifmetikadan foydalaning. Quyida bunga misol ${ Displaystyle 3 ^ {50}}$ mod 50:
   • Ifodani qulayroq shaklda qayta yozing: ${ Displaystyle (3 ^ {25} * 3 ^ {25})}$ mod 50. Qo'lda hisob -kitoblar yanada soddalashtirishni talab qilishi mumkin.
   • ${ Displaystyle (3 ^ {25} * 3 ^ {25})}$ mod 50 = ${ Displaystyle (3 ^ {25}}$ mod 50 ${ Displaystyle * 3 ^ {25}}$ mod 50) mod 50. Bu erda biz modulli ko'paytirish xususiyatini hisobga oldik.
   • ${ Displaystyle 3 ^ {25}}$ mod 50 = 43.
   • ${ Displaystyle (3 ^ {25}}$ mod 50 ${ Displaystyle * 3 ^ {25}}$ mod 50) mod 50 = ${ Displaystyle (43 * 43)}$ mod 50.
   • ${ Displaystyle = 1849}$ mod 50.
   • ${ Displaystyle = 49}$.

3dan 3 qism: Xitoy qoldiqlari teoremasidan foydalanish

1. 1 Ikki raqamni tanlang. Raqamlardan biri kompozitsion bo'lishi kerak, ikkinchisi esa soddalik uchun tekshirmoqchi bo'lgan raqam bo'lishi kerak.
   • Raqam 1 = 35
   • Raqam 2 = 97
2. 2 Noldan katta va mos ravishda Number1 va Number2 raqamlaridan past bo'lgan ikkita qiymatni tanlang. Bu qiymatlar bir xil bo'lmasligi kerak.
   • Qiymat1 = 1
   • Qiymat 2 = 2
3. 3 1 -son va 2 -sonli MMI (matematik ko'paytma teskari) ni hisoblang.
   • MMI ni hisoblang
     • MMI1 = Number2 ^ -1 Mod Number1
     • MMI2 = Number1 ^ -1 Mod Number2
   • Faqat oddiy sonlar uchun (bu kompozit sonlar uchun raqam beradi, lekin bu uning MMI bo'lmaydi):
     • MMI1 = (Number2 ^ (Number1-2))% Number1
     • MMI2 = (Number1 ^ (Number2-2))% Number2
   • Misol uchun:
     • MMI1 = (97 ^ 33)% 35
     • MMI2 = (35 ^ 95)% 97
4. 4 Log2 modullariga qadar har bir MMI uchun jadval yarating:
   • MMI1 uchun
     • F (1) = Raqam 2% Son1 = 97% 35 = 27
     • F (2) = F (1) * F (1)% Raqam1 = 27 * 27% 35 = 29
     • F (4) = F (2) * F (2)% Raqam1 = 29 * 29% 35 = 1
     • F (8) = F (4) * F (4)% Raqam1 = 1 * 1% 35 = 1
     • F (16) = F (8) * F (8)% Raqam1 = 1 * 1% 35 = 1
     • F (32) = F (16) * F (16)% Raqam1 = 1 * 1% 35 = 1
   • Birlashtirilgan raqamlarni hisoblang 1-2
     • 35 -2 = 33 (10001) tayanch 2
     • MMI1 = F (33) = F (32) * F (1) mod 35
     • MMI1 = F (33) = 1 * 27 mod 35
     • MMI1 = 27
   • MMI2 uchun
     • F (1) = Son1% Raqam2 = 35% 97 = 35
     • F (2) = F (1) * F (1)% Raqam2 = 35 * 35 mod 97 = 61
     • F (4) = F (2) * F (2)% Raqam2 = 61 * 61 mod 97 = 35
     • F (8) = F (4) * F (4)% Raqam2 = 35 * 35 mod 97 = 61
     • F (16) = F (8) * F (8)% Raqam2 = 61 * 61 mod 97 = 35
     • F (32) = F (16) * F (16)% Raqam2 = 35 * 35 mod 97 = 61
     • F (64) = F (32) * F (32)% Raqam2 = 61 * 61 mod 97 = 35
     • F (128) = F (64) * F (64)% Raqam2 = 35 * 35 mod 97 = 61
   • 2 - 2 juft raqamini hisoblang
     • 97 - 2 = 95 = (1011111) tayanch 2
     • MMI2 = ((((((F (64) * F (16)% 97) * F (8)% 97) * F (4)% 97) * F (2)% 97) * F (1)% 97)
     • MMI2 = ((((((35 * 35)% 97) * 61)% 97) * 35% 97) * 61% 97) * 35% 97)
     • MMI2 = 61
5. 5 Hisoblang (Value1 * Number2 * MMI1 + Value2 * Number1 * MMI2)% (Number1 * Number2)
   • Javob = (1 * 97 * 27 + 2 * 35 * 61)% (97 * 35)
   • Javob = (2619 + 4270)% 3395
   • Javob = 99
6. 6 Number1 asosiy emasligini tekshiring
   • Hisoblang (Javob - Qiymat1)% Raqam1
   • 99 – 1 % 35 = 28
   • 28 0 dan katta bo'lgani uchun, 35 oddiy son emas.
7. 7 Number2 asosiy ekanligini tekshiring.
   • Hisoblang (Javob - Qiymat2)% Raqam2
   • 99 – 2 % 97 = 0
   • 0 0 bo'lgani uchun, 97, ehtimol, asosiy son.
8. 8 1 dan 7 gacha bo'lgan bosqichlarni kamida ikki marta takrorlang.
   • Agar 7 -bosqichda 0 bo'lsa:
     • Agar Number1 asosiy bo'lmasa, boshqa Number1 -dan foydalaning.
     • Agar Number1 asosiy bo'lsa, boshqa Number1 -dan foydalaning. Bunday holda, siz 6 va 7 -bosqichlarda 0 olishingiz kerak.
     • Turli ma'no1 va ma'no2 dan foydalaning.
   • Agar 7 -bosqichda siz doimo 0 ga ega bo'lsangiz, unda 2 -raqam birinchi o'rinni egallashi mumkin.
   • 1 -dan 7 -gacha bo'lgan qadamlar, agar Number1 asosiy bo'lmasa va Number2 Number1 -ning bo'linuvchisi bo'lsa, xatoga olib kelishi mumkin. Ta'riflangan usul har ikkala raqam ham boshlanganda ishlaydi.
   • 1 dan 7 gacha bo'lgan qadamlarni takrorlashingiz kerak bo'lgan sabab shundaki, ba'zi hollarda, hatto 1 -raqam va 2 -son boshlang'ich bo'lmasa ham, 7 -bosqichda siz 0 (bitta yoki ikkala raqam uchun) olasiz. Bu kamdan -kam hollarda bo'ladi.Boshqa Number1 (kompozit) ni tanlang, va agar Number2 asosiy bo'lmasa, 7 -bosqichda Number2 nolga teng bo'lmaydi (Number1 Number2 ning bo'linuvchisi bo'lgan hollar bundan mustasno - bu erda 7 -bosqichda tub sonlar har doim nolga teng bo'ladi).

Maslahatlar

• 168 dan 1000 gacha asosiy raqamlar: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79 , 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211 , 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359 , 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509 , 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673 , 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853 , 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997.
• Katta raqamlar bilan ishlashda qo'pol kuch sinovi zerikarli sinov bo'lsa -da, bu kichik sonlar uchun juda samarali. Hatto ko'p sonli bo'lsa ham, kichik bo'linuvchilarni sinashdan boshlang, so'ngra raqamlarning soddaligini tekshirishning yanada murakkab usullariga o'ting (agar kichik bo'linuvchilar topilmasa).

Sizga nima kerak

• Qog'oz, qalam yoki kompyuter