Saturs

• Soļi
• 1. daļa no 3: Vienkāršības testi
• 2. daļa no 3: Kā darbojas vienkāršības testi
• 3. daļa no 3: Ķīnas atlikuma teorēmas izmantošana
• Padomi
• Ko tev vajag

Pirmskaitļi ir skaitļi, kas dalās tikai ar sevi un ar 1. Visus pārējos skaitļus sauc par saliktiem skaitļiem. Ir daudz veidu, kā noteikt, vai skaitlis ir galvenais, un tiem visiem ir savas priekšrocības un trūkumi. No vienas puses, dažas metodes ir ļoti precīzas, taču tās ir diezgan sarežģītas, ja jums ir darīšana ar lieliem skaitļiem. No otras puses, ir daudz ātrāki veidi, taču tie var novest pie nepareiziem rezultātiem. Atbilstošās metodes izvēle ir atkarīga no tā, cik lieli skaitļi jūs strādājat.

Soļi

1. daļa no 3: Vienkāršības testi

Piezīme: visās formulās n apzīmē pārbaudāmo numuru.

1. 1 Dalītāju uzskaitījums. Pietiek sadalīt n uz visiem pirmskaitļiem no 2 līdz noapaļotajai vērtībai (${ displaystyle { sqrt {n}}}$).
2. 2 Fermata mazā teorēma. Brīdinājums: dažreiz tests kļūdaini identificē saliktos skaitļus kā galvenos, pat visām a vērtībām.
   • Izvēlēsimies veselu skaitli atā, lai 2 ≤ a ≤ n - 1.
   • Ja a (mod n) = a (mod n), tad skaitlis, iespējams, ir galvenais. Ja vienlīdzība nav izpildīta, skaitlis n ir salikts.
   • Pārbaudiet doto vienādību vairākām vērtībām alai palielinātu varbūtību, ka pārbaudītais skaitlis patiešām ir galvenais.
3. 3 Millera-Rabina tests. Brīdinājums: dažreiz, lai gan reti, vairākām a vērtībām tests kļūdaini identificē saliktos skaitļus kā galvenos.
   • Atrodiet daudzumus s un d tā, lai ${ displaystyle n-1 = 2 ^ {s} * d}$.
   • Izvēlieties veselu skaitli a diapazonā 2 ≤ a ≤ n - 1.
   • Ja a = +1 (mod n) vai -1 (mod n), tad n, iespējams, ir galvenais. Šajā gadījumā dodieties uz testa rezultātu. Ja vienlīdzība nav spēkā, pārejiet pie nākamās darbības.
   • Solidējiet savu atbildi (${ displaystyle a ^ {2d}}$). Ja iegūstat -1 (mod n), tad n, iespējams, ir pirmskaitlis. Šajā gadījumā dodieties uz testa rezultātu. Ja vienlīdzība neizdodas, atkārtojiet (${ displaystyle a ^ {4d}}$ un tā tālāk) līdz ${ displaystyle a ^ {2 ^ {s-1} d}}$.
   • Ja kādā solī pēc kvadrāta skaitļa, kas nav ${ displaystyle pm 1}$ (mod n), jums ir +1 (mod n), tātad n ir salikts skaitlis. Ja ${ displaystyle a ^ {2 ^ {s-1} d} neq pm 1}$ (mod n), tad n nav galvenais.
   • Testa rezultāts: ja n nokārto pārbaudi, atkārtojiet to citām vērtībām alai palielinātu pārliecību.

2. daļa no 3: Kā darbojas vienkāršības testi

1. 1 Dalītāju uzskaitījums. Pēc definīcijas skaitlis n ir vienkāršs tikai tad, ja tas nav dalāms ar 2 un citiem veseliem skaitļiem, izņemot 1 un pats. Iepriekš minētā formula ļauj noņemt nevajadzīgas darbības un ietaupīt laiku: piemēram, pēc pārbaudes, vai skaitlis dalās ar 3, nav jāpārbauda, ​​vai tas dalās ar 9.
   • Grīdas (x) funkcija noapaļo x līdz tuvākajam veselam skaitlim, kas mazāks vai vienāds ar x.
2. 2 Uzziniet par moduļu aritmētiku. Operācija "x mod y" (mod ir latīņu vārda "modulo" saīsinājums, tas ir, "modulis") nozīmē "sadaliet x ar y un atrodiet atlikumu". Citiem vārdiem sakot, modulārā aritmētikā, sasniedzot noteiktu vērtību, ko sauc modulis, skaitļi atkal "pagriežas" uz nulli. Piemēram, pulkstenis tiek skaitīts atpakaļ ar 12. moduli: tas rāda 10, 11 un 12 stundas un pēc tam atgriežas pie 1.
   • Daudziem kalkulatoriem ir mod atslēga. Šīs sadaļas beigās ir parādīts, kā manuāli aprēķināt šo funkciju lieliem skaitļiem.
3. 3 Uzziniet par Fermata mazās teorēmas nepilnībām. Visi skaitļi, kuriem nav izpildīti testa nosacījumi, ir salikti, bet pārējie skaitļi ir tikai droši vien ir vienkārši. Ja vēlaties izvairīties no nepareiziem rezultātiem, meklējiet n sarakstā "Carmichael numuri" (saliktie skaitļi, kas atbilst šim testam) un "Fermat pseidoprime skaitļi" (šie skaitļi atbilst testa nosacījumiem tikai dažām vērtībām) a).
4. 4 Ja tas ir ērti, izmantojiet Millera-Rabina testu. Lai gan šī metode ir diezgan apgrūtinoša manuāliem aprēķiniem, to bieži izmanto datorprogrammās. Tas nodrošina pieņemamu ātrumu un mazāk kļūdu nekā Fermat metode. Saliktais skaitlis netiks uzskatīts par galveno skaitli, ja aprēķini tiek veikti vairāk nekā ¼ vērtībām a... Ja nejauši izvēlaties dažādas vērtības a un visiem tiem tests dos pozitīvu rezultātu, mēs varam ar diezgan lielu pārliecību pieņemt, ka n ir pirmskaitlis.
5. 5 Lieliem skaitļiem izmantojiet moduļu aritmētiku. Ja jums nav pa rokai mod kalkulators vai kalkulators nav paredzēts tik lielu skaitļu apstrādei, izmantojiet jaudas īpašības un modulāro aritmētiku, lai atvieglotu aprēķinus. Zemāk ir piemērs ${ displaystyle 3 ^ {50}}$ mod 50:
   • Pārrakstiet izteiksmi ērtākā formā: ${ displaystyle (3 ^ {25} * 3 ^ {25})}$ mod 50. Manuāliem aprēķiniem var būt nepieciešami papildu vienkāršojumi.
   • ${ displaystyle (3 ^ {25} * 3 ^ {25})}$ mod 50 = ${ displaystyle (3 ^ {25}})$ mod 50 ${ displaystyle * 3 ^ {25}}$ mod 50) mod 50. Šeit mēs ņēmām vērā moduļu reizināšanas īpašību.
   • ${ 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}$.

3. daļa no 3: Ķīnas atlikuma teorēmas izmantošana

1. 1 Izvēlieties divus ciparus. Vienam no skaitļiem ir jābūt saliktam, bet otram jābūt tieši tādam, kuru vēlaties pārbaudīt vienkāršības dēļ.
   • Skaitlis 1 = 35
   • Skaitlis 2 = 97
2. 2 Atlasiet divas vērtības, kas ir lielākas par nulli un attiecīgi mazākas par skaitļiem Skaitlis1 un Skaitlis2. Šīs vērtības nedrīkst būt vienādas.
   • Vērtība1 = 1
   • Vērtība2 = 2
3. 3 Aprēķiniet MMI (matemātisko multiplikatīvo apgriezto skaitli 1 un skaitli 2).
   • Aprēķināt MMI
     • MMI1 = Skaitlis2 ^ -1 Mod Skaitlis1
     • MMI2 = Skaitlis1 ^ -1 Mod Skaitlis2
   • Tikai pirmskaitļiem (tas dos skaitli saliktiem skaitļiem, bet tas nebūs viņa MMI):
     • MMI1 = (Skaitlis2 ^ (Skaitlis1-2))% Skaitlis1
     • MMI2 = (Skaitlis1 ^ (Skaitlis2-2))% Skaitlis2
   • Piemēram:
     • MMI1 = (97 ^ 33)% 35
     • MMI2 = (35 ^ 95)% 97
4. 4 Izveidojiet tabulu katram MMI līdz log2 moduļiem:
   • MMI1
     • F (1) = skaitlis2% skaitlis1 = 97% 35 = 27
     • F (2) = F (1) * F (1)% Skaitlis1 = 27 * 27% 35 = 29
     • F (4) = F (2) * F (2)% Skaitlis1 = 29 * 29% 35 = 1
     • F (8) = F (4) * F (4)% Skaitlis1 = 1 * 1% 35 = 1
     • F (16) = F (8) * F (8)% Skaitlis1 = 1 * 1% 35 = 1
     • F (32) = F (16) * F (16)% Skaitlis1 = 1 * 1% 35 = 1
   • Aprēķiniet pāra skaitļus 1 - 2
     • 35 -2 = 33 (10001) bāze 2
     • MMI1 = F (33) = F (32) * F (1) mod 35
     • MMI1 = F (33) = 1 * 27 mod 35
     • MMI1 = 27
   • MMI2
     • F (1) = skaitlis1% skaitlis2 = 35% 97 = 35
     • F (2) = F (1) * F (1)% Skaitlis2 = 35 * 35 mod 97 = 61
     • F (4) = F (2) * F (2)% Skaitlis2 = 61 * 61 mod 97 = 35
     • F (8) = F (4) * F (4)% Skaitlis2 = 35 * 35 mod 97 = 61
     • F (16) = F (8) * F (8)% Skaitlis2 = 61 * 61 mod 97 = 35
     • F (32) = F (16) * F (16)% Skaitlis2 = 35 * 35 mod 97 = 61
     • F (64) = F (32) * F (32)% Skaitlis2 = 61 * 61 mod 97 = 35
     • F (128) = F (64) * F (64)% Skaitlis2 = 35 * 35 mod 97 = 61
   • Aprēķiniet pāra skaitli 2 - 2
     • 97 - 2 = 95 = (1011111) 2. bāze
     • 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 Aprēķināt (Value1 * Number2 * MMI1 + Value2 * Number1 * MMI2)% (Number1 * Number2)
   • Atbilde = (1 * 97 * 27 + 2 * 35 * 61)% (97 * 35)
   • Atbilde = (2619 + 4270)% 3395
   • Atbilde = 99
6. 6 Pārbaudiet, vai skaitlis 1 nav galvenais
   • Aprēķināt (Atbilde - Vērtība1)% Skaitlis1
   • 99 – 1 % 35 = 28
   • Tā kā 28 ir lielāks par 0, 35 nav primārais skaitlis.
7. 7 Pārbaudiet, vai skaitlis 2 ir galvenais.
   • Aprēķināt (Atbilde - Vērtība2)% Skaitlis2
   • 99 – 2 % 97 = 0
   • Tā kā 0 ir 0, visticamāk, 97 ir galvenais skaitlis.
8. 8 Atkārtojiet 1. līdz 7. darbību vēl vismaz divas reizes.
   • Ja 7. solī saņemat 0:
     • Izmantojiet citu skaitli1, ja skaitlis1 nav galvenais.
     • Izmantojiet citu skaitli1, ja skaitlis1 ir galvenais. Šādā gadījumā 6. un 7. darbībā vajadzētu iegūt 0.
     • Izmantojiet dažādas nozīmes1 un nozīmes2.
   • Ja 7. solī jūs pastāvīgi saņemat 0, tad ļoti iespējams, ka skaitlis 2 būs galvenais.
   • 1. līdz 7. darbība var izraisīt kļūdu, ja skaitlis1 nav galvenais un skaitlis2 ir skaitļa1 dalītājs. Aprakstītā metode darbojas visos gadījumos, kad abi skaitļi ir primāri.
   • Jums ir jāatkārto 1. līdz 7. darbība, jo dažos gadījumos, pat ja skaitlis 1 un skaitlis 2 nav galvenie, 7. solī jūs iegūsit 0 (vienam vai abiem skaitļiem). Tas notiek reti.Izvēlieties citu skaitli1 (salikts), un, ja skaitlis2 nav primārais, tad skaitlis2 7. solī nebūs vienāds ar nulli (izņemot gadījumu, kad skaitlis1 ir skaitļa2 dalītājs - šeit 7. solī primīši vienmēr būs vienādi ar nulli).

Padomi

• Sākotnējie skaitļi no 168 līdz 1000: 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.
• Lai gan brutālā spēka pārbaude ir garlaicīgs tests, strādājot ar lieliem skaitļiem, tas ir diezgan efektīvs maziem skaitļiem. Pat lielu skaitļu gadījumā vispirms pārbaudiet mazos dalītājus un pēc tam pārejiet pie sarežģītākām skaitļu vienkāršības pārbaudes metodēm (ja netiek atrasti mazi dalītāji).

Ko tev vajag

• Papīrs, pildspalva vai dators