Indhold

• Trin
• Del 1 af 3: Enkelhedstests
• Del 2 af 3: Sådan fungerer enkelhedstests
• Del 3 af 3: Brug af den kinesiske restsats
• Tips
• Hvad har du brug for

Primtal er tal, der kun kan deles af sig selv og med 1. Alle andre tal kaldes sammensatte tal. Der er mange måder at afgøre, om et tal er primtal, og de har alle deres egne fordele og ulemper. På den ene side er nogle af metoderne meget præcise, men de er ret komplekse, hvis du har at gøre med store tal. På den anden side er der meget hurtigere måder, men de kan føre til forkerte resultater. Valget af den passende metode afhænger af, hvor store de tal, du arbejder med.

Trin

Del 1 af 3: Enkelhedstests

Bemærk: i alle formler n angiver det nummer, der skal kontrolleres.

1. 1 Optælling af delere. Det er nok at dele op n til alle primtal fra 2 til den afrundede værdi (${ displaystyle { sqrt {n}}}$).
2. 2 Fermats lille sætning. Advarsel: undertiden vil testen fejlagtigt identificere sammensatte tal som primtal, selv for alle værdier af a.
   • Lad os vælge et helt tal -ensådan at 2 ≤ a ≤ n - 1.
   • Hvis a (mod n) = a (mod n) så er tallet sandsynligvis primtal. Hvis ligestillingen ikke er opfyldt, er tallet n sammensat.
   • Kontroller den givne lighed for flere værdier -enfor at øge sandsynligheden for, at det antal, der testes, faktisk er primært.
3. 3 Miller-Rabin test. Advarsel: nogle gange, selvom det sjældent er, for flere værdier af a, vil testen fejlagtigt identificere sammensatte tal som primtal.
   • Find mængderne s og d sådan at ${ displaystyle n-1 = 2 ^ {s} * d}$.
   • Vælg et helt tal -en i området 2 ≤ a ≤ n - 1.
   • Hvis a = +1 (mod n) eller -1 (mod n), så er n sandsynligvis primtal. I dette tilfælde skal du gå til testresultatet. Hvis ligestillingen ikke holder, skal du gå til næste trin.
   • Firkant dit svar (${ displaystyle a ^ {2d}}$). Hvis du får -1 (mod n), så er n sandsynligvis et primtal. I dette tilfælde skal du gå til testresultatet. Hvis ligestillingen fejler, gentag (${ displaystyle a ^ {4d}}$ og så videre) indtil ${ displaystyle a ^ {2 ^ {s-1} d}}$.
   • Hvis på et eller andet trin efter kvadrering et andet tal end ${ displaystyle pm 1}$ (mod n), du har +1 (mod n), så n er et sammensat tal. Hvis ${ displaystyle a ^ {2 ^ {s-1} d} neq pm 1}$ (mod n), så er n ikke prime.
   • Testresultat: hvis n består testen, gentages den for andre værdier -enat øge tilliden.

Del 2 af 3: Sådan fungerer enkelhedstests

1. 1 Optælling af delere. Per definition nummeret n er kun enkel, hvis den ikke er delelig med 2 og andre heltal undtagen 1 og sig selv. Ovenstående formel giver dig mulighed for at fjerne unødvendige trin og spare tid: for eksempel efter at have kontrolleret, om et tal er deleligt med 3, er det ikke nødvendigt at kontrollere, om det er delbart med 9.
   • Gulvfunktionen (x) afrunder x til det nærmeste heltal mindre end eller lig med x.
2. 2 Lær mere om modulær regning. Operationen "x mod y" (mod er en forkortelse af det latinske ord "modulo", det vil sige "modul") betyder "dividere x med y og finde resten." Med andre ord, i modulær regning, når man når en bestemt værdi, som kaldes modul, tallene "vender" til nul igen. For eksempel tæller uret ned med modul 12: det viser 10, 11 og 12 timer og vender derefter tilbage til 1.
   • Mange lommeregnere har en mod -nøgle. Slutningen af ​​dette afsnit viser dig, hvordan du manuelt beregner denne funktion for store tal.
3. 3 Lær om faldgruberne i Fermats lille sætning. Alle tal, for hvilke testbetingelserne ikke er opfyldt, er sammensatte, men resten af ​​tallene er kun sandsynligvis er enkle. Hvis du vil undgå forkerte resultater, skal du søge n på listen over "Carmichael -numre" (sammensatte tal, der opfylder denne test) og "Fermat -pseudoprime -numre" (disse tal opfylder testbetingelserne kun for nogle værdier -en).
4. 4 Hvis det er praktisk, skal du bruge Miller-Rabin-testen. Selvom denne metode er temmelig besværlig til manuelle beregninger, bruges den ofte i computerprogrammer. Det giver acceptabel hastighed og færre fejl end Fermats metode. Et sammensat tal tages ikke som et primtal, hvis der udføres beregninger for mere end ¼ værdier -en... Hvis du tilfældigt vælger forskellige værdier -en og for dem alle vil testen give et positivt resultat, det kan vi med en temmelig høj grad af tillid antage n er et primtal.
5. 5 For store tal, brug modulær regning. Hvis du ikke har en mod -lommeregner ved hånden, eller hvis lommeregneren ikke er designet til at håndtere så store tal, skal du bruge strømegenskaber og modulregning til at gøre beregningerne lettere. Nedenfor er et eksempel på ${ displaystyle 3 ^ {50}}$ mod 50:
   • Omskriv udtrykket i en mere bekvem form: ${ displaystyle (3 ^ {25} * 3 ^ {25})}$ mod 50. Manuelle beregninger kan kræve yderligere forenklinger.
   • ${ displaystyle (3 ^ {25} * 3 ^ {25})}$ mod 50 = ${ displaystyle (3 ^ {25}}$ mod 50 ${ displaystyle * 3 ^ {25}}$ mod 50) mod 50. Her tog vi hensyn til egenskaben ved modulær multiplikation.
   • ${ 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}$.

Del 3 af 3: Brug af den kinesiske restsats

1. 1 Vælg to tal. Et af tallene skal være sammensat, og det andet skal være præcis det, du vil teste for enkelhed.
   • Nummer 1 = 35
   • Nummer2 = 97
2. 2 Vælg to værdier, der er større end nul og henholdsvis mindre end tallene Number1 og Number2. Disse værdier må ikke være de samme.
   • Værdi1 = 1
   • Værdi2 = 2
3. 3 Beregn MMI (Mathematical Multiplicative Inverse) for Number1 og Number2.
   • Beregn MMI
     • MMI1 = Number2 ^ -1 Mod Number1
     • MMI2 = Number1 ^ -1 Mod Number2
   • Kun for primtal (dette giver et tal for sammensatte tal, men det er ikke hans MMI):
     • MMI1 = (Number2 ^ (Number1-2))% Number1
     • MMI2 = (Number1 ^ (Number2-2))% Number2
   • For eksempel:
     • MMI1 = (97 ^ 33)% 35
     • MMI2 = (35 ^ 95)% 97
4. 4 Opret en tabel for hver MMI ned til log2 -moduler:
   • Til MMI1
     • F (1) = Antal2% Antal1 = 97% 35 = 27
     • F (2) = F (1) * F (1)% Antal1 = 27 * 27% 35 = 29
     • F (4) = F (2) * F (2)% Antal1 = 29 * 29% 35 = 1
     • F (8) = F (4) * F (4)% Antal1 = 1 * 1% 35 = 1
     • F (16) = F (8) * F (8)% Antal1 = 1 * 1% 35 = 1
     • F (32) = F (16) * F (16)% Antal1 = 1 * 1% 35 = 1
   • Beregn parrede numre 1-2
     • 35 -2 = 33 (10001) base 2
     • MMI1 = F (33) = F (32) * F (1) mod 35
     • MMI1 = F (33) = 1 * 27 mod 35
     • MMI1 = 27
   • Til MMI2
     • F (1) = Antal1% Antal2 = 35% 97 = 35
     • F (2) = F (1) * F (1)% Antal2 = 35 * 35 mod 97 = 61
     • F (4) = F (2) * F (2)% Antal2 = 61 * 61 mod 97 = 35
     • F (8) = F (4) * F (4)% Antal2 = 35 * 35 mod 97 = 61
     • F (16) = F (8) * F (8)% Antal2 = 61 * 61 mod 97 = 35
     • F (32) = F (16) * F (16)% Antal2 = 35 * 35 mod 97 = 61
     • F (64) = F (32) * F (32)% Antal2 = 61 * 61 mod 97 = 35
     • F (128) = F (64) * F (64)% Antal2 = 35 * 35 mod 97 = 61
   • Beregn det parrede nummer 2 - 2
     • 97 - 2 = 95 = (1011111) base 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 Beregn (værdi1 * tal2 * MMI1 + værdi2 * tal1 * MMI2)% (tal1 * tal2)
   • Svar = (1 * 97 * 27 + 2 * 35 * 61)% (97 * 35)
   • Svar = (2619 + 4270)% 3395
   • Svar = 99
6. 6 Kontroller, at nummer 1 ikke er primtal
   • Beregn (Svar - Værdi1)% Antal1
   • 99 – 1 % 35 = 28
   • Da 28 er større end 0, er 35 ikke et primtal.
7. 7 Kontroller, at Number2 er primtal.
   • Beregn (svar - værdi2)% tal2
   • 99 – 2 % 97 = 0
   • Da 0 er 0, er 97 sandsynligvis et primtal.
8. 8 Gentag trin 1 til 7 mindst to gange mere.
   • Hvis du får 0 i trin 7:
     • Brug et andet nummer1, hvis tal1 ikke er primtal.
     • Brug et andet nummer1, hvis nummer 1 er primtal. I dette tilfælde skal du få 0 i trin 6 og 7.
     • Brug forskellig Betydning1 og Betydning2.
   • Hvis du i trin 7 konsekvent får 0, er nummer 2 sandsynligvis primært.
   • Trin 1 til og med 7 kan resultere i en fejl, hvis nummer 1 ikke er primtal, og nummer 2 er en divisor for nummer1. Den beskrevne metode fungerer i alle tilfælde, hvor begge tal er primtallige.
   • Grunden til, at du skal gentage trin 1 til 7, er fordi i nogle tilfælde, selvom nummer 1 og nummer 2 ikke er primtal, får du i trin 7 0 (for et eller begge tal). Dette sker sjældent.Vælg en anden Number1 (sammensat), og hvis Number2 ikke er primtal, vil Number2 ikke være lig med nul i trin 7 (undtagen tilfældet, hvor Number1 er en divisor for Number2 - her vil primtal altid være lig nul i trin 7).

Tips

• Primtal fra 168 til 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.
• Selvom test af brute force er en kedelig test, når man arbejder med store tal, er den ret effektiv til små tal. Selv i tilfælde af store tal skal du starte med at teste små divisorer og derefter gå videre til mere sofistikerede metoder til at kontrollere enkelheden af ​​tal (hvis der ikke findes små divisorer).

Hvad har du brug for

• Papir, pen eller computer