Inhoud

• Stappen
• Deel 1 van 3: Tests van eenvoud
• Deel 2 van 3: Hoe eenvoudstests werken
• Deel 3 van 3: De Chinese Reststelling gebruiken
• Tips
• Wat heb je nodig

Priemgetallen zijn getallen die alleen door zichzelf en door 1 deelbaar zijn. Alle andere getallen worden samengestelde getallen genoemd. Er zijn veel manieren om te bepalen of een getal een priemgetal is, en ze hebben allemaal hun eigen voor- en nadelen. Enerzijds zijn sommige methoden zeer nauwkeurig, maar ze zijn behoorlijk complex als je met grote aantallen te maken hebt. Aan de andere kant zijn er veel snellere manieren, maar deze kunnen tot onjuiste resultaten leiden. De keuze van de juiste methode hangt af van hoe groot de getallen zijn waarmee u werkt.

Stappen

Deel 1 van 3: Tests van eenvoud

Opmerking: in alle formules N geeft het te controleren nummer aan.

1. 1 Opsomming van delers. Het is genoeg om te verdelen N naar alle priemgetallen van 2 tot de afgeronde waarde (${ weergavestijl { sqrt {n}}}$).
2. 2 De kleine stelling van Fermat. Waarschuwing: soms identificeert de test samengestelde getallen ten onrechte als priemgetallen, zelfs voor alle waarden van a.
   • Laten we een geheel getal kiezen eenzodat 2 ≤ a ≤ n - 1.
   • Als a (mod n) = a (mod n) dan is het getal waarschijnlijk priemgetal. Als niet aan de gelijkheid wordt voldaan, is het getal n samengesteld.
   • Controleer gegeven gelijkheid voor meerdere waarden eenom de kans te vergroten dat het geteste getal inderdaad een priemgetal is.
3. 3 Miller-Rabin-test. Waarschuwing: soms, hoewel zelden, voor meerdere waarden van a, identificeert de test samengestelde getallen ten onrechte als priemgetallen.
   • Vind de hoeveelheden s en d zodanig dat ${ displaystyle n-1 = 2 ^ {s} * d}$.
   • Selecteer een geheel getal een in het bereik 2 ≤ a ≤ n - 1.
   • Als a = +1 (mod n) of -1 (mod n), dan is n waarschijnlijk een priemgetal. Ga in dit geval naar het testresultaat. Als de gelijkheid niet geldt, gaat u naar de volgende stap.
   • Vier je antwoord (${ weergavestijl a ^ {2}d}}$). Als je -1 krijgt (mod n), dan is n waarschijnlijk een priemgetal. Ga in dit geval naar het testresultaat. Als de gelijkheid mislukt, herhaal dan (${ weergavestijl a ^ {4d}}$ enzovoort) tot ${ weergavestijl a ^ {2 ^ {s-1} d}}$.
   • Als op een bepaalde stap na het kwadrateren van een ander getal dan ${ weergavestijl pm 1}$ (mod n), je hebt +1 (mod n), dus n is een samengesteld getal. Indien ${ displaystyle a ^ {2 ^ {s-1} d} neq pm 1}$ (mod n), dan is n geen priemgetal.
   • Testresultaat: als n de test doorstaat, herhaal deze dan voor andere waarden eenom het vertrouwen te vergroten.

Deel 2 van 3: Hoe eenvoudstests werken

1. 1 Opsomming van delers. Per definitie is het nummer N is alleen eenvoudig als het niet deelbaar is door 2 en andere gehele getallen behalve 1 en zichzelf. Met de bovenstaande formule kunt u onnodige stappen verwijderen en tijd besparen: als u bijvoorbeeld hebt gecontroleerd of een getal deelbaar is door 3, hoeft u niet te controleren of het deelbaar is door 9.
   • De functie verdieping (x) rondt x af op het dichtstbijzijnde gehele getal kleiner dan of gelijk aan x.
2. 2 Leer meer over modulaire rekenkunde. De bewerking "x mod y" (mod is een afkorting van het Latijnse woord "modulo", dat wil zeggen "module") betekent "deel x door y en vind de rest." Met andere woorden, in modulaire rekenkunde, bij het bereiken van een bepaalde waarde, die wordt genoemd module, de cijfers "draaien" weer naar nul. De klok telt bijvoorbeeld af met module 12: hij geeft 10, 11 en 12 uur aan, en keert dan terug naar 1.
   • Veel rekenmachines hebben een mod-toets. Aan het einde van dit gedeelte ziet u hoe u deze functie handmatig kunt berekenen voor grote getallen.
3. 3 Leer meer over de valkuilen van de kleine stelling van Fermat. Alle getallen waarvoor niet aan de testvoorwaarden wordt voldaan, zijn samengesteld, maar de rest van de getallen zijn alleen waarschijnlijk zijn eenvoudig. Als u onjuiste resultaten wilt voorkomen, zoekt u N in de lijst van "Carmichael-getallen" (samengestelde getallen die voldoen aan deze test) en "Fermat pseudoprime-getallen" (deze getallen voldoen slechts voor sommige waarden aan de testvoorwaarden een).
4. 4 Gebruik indien handig de Miller-Rabin-test. Hoewel deze methode nogal omslachtig is voor handmatige berekeningen, wordt ze vaak gebruikt in computerprogramma's. Het biedt een acceptabele snelheid en minder fouten dan de methode van Fermat. Een samengesteld getal wordt niet als priemgetal beschouwd als berekeningen worden uitgevoerd voor meer dan ¼ waarden een... Als u willekeurig verschillende waarden kiest een en voor alle van hen zal de test een positief resultaat geven, we kunnen met een vrij hoge mate van vertrouwen aannemen dat: N is een priemgetal.
5. 5 Gebruik voor grote getallen modulaire rekenkunde. Als je geen mod-calculator bij de hand hebt, of als de rekenmachine niet is ontworpen om zulke grote getallen aan te kunnen, gebruik dan power-eigenschappen en modulaire rekenkunde om de berekeningen gemakkelijker te maken. Hieronder is een voorbeeld voor: ${ weergavestijl 3 ^ {50}}$ mod 50:
   • Herschrijf de uitdrukking in een handiger vorm: ${ weergavestijl (3 ^ {25} * 3 ^ {25})}$ mod 50. Handmatige berekeningen kunnen verdere vereenvoudigingen vereisen.
   • ${ weergavestijl (3 ^ {25} * 3 ^ {25})}$ mod 50 = ${ weergavestijl (3 ^ {25}}$ mod 50 ${ weergavestijl * 3 ^ {25}}$ mod 50) mod 50. Hier hebben we rekening gehouden met de eigenschap van modulaire vermenigvuldiging.
   • ${ weergavestijl 3 ^ {25}}$ mod 50 = 43.
   • ${ weergavestijl (3 ^ {25}}$ mod 50 ${ weergavestijl * 3 ^ {25}}$ mod 50) mod 50 = ${ weergavestijl (43 * 43)}$ mod 50.
   • ${ weergavestijl = 1849}$ mod 50.
   • ${ weergavestijl = 49}$.

Deel 3 van 3: De Chinese Reststelling gebruiken

1. 1 Kies twee nummers. Een van de getallen moet samengesteld zijn en de andere moet precies het getal zijn dat u voor de eenvoud wilt testen.
   • Getal1 = 35
   • Getal2 = 97
2. 2 Selecteer twee waarden die groter zijn dan nul en respectievelijk kleiner dan de getallen Number1 en Number2. Deze waarden mogen niet hetzelfde zijn.
   • Waarde1 = 1
   • Waarde2 = 2
3. 3 Bereken de MMI (Mathematical Multiplicatieve Inverse) voor Number1 en Number2.
   • Bereken MMI
     • MMI1 = Nummer2 ^ -1 Mod Nummer1
     • MMI2 = Nummer1 ^ -1 Mod Nummer2
   • Alleen voor priemgetallen (dit geeft een getal voor samengestelde getallen, maar het zal niet zijn MMI zijn):
     • MMI1 = (nummer2 ^ (nummer1-2))% nummer1
     • MMI2 = (nummer1 ^ (nummer2-2))% nummer2
   • Bijvoorbeeld:
     • MMI1 = (97 ^ 33)% 35
     • MMI2 = (35 ^ 95)% 97
4. 4 Maak een tabel voor elke MMI tot aan log2-modules:
   • Voor MMI1
     • F (1) = Getal2% Getal1 = 97% 35 = 27
     • F (2) = F (1) * F (1)% Getal1 = 27 * 27% 35 = 29
     • F (4) = F (2) * F (2)% Getal1 = 29 * 29% 35 = 1
     • F (8) = F (4) * F (4)% Getal1 = 1 * 1% 35 = 1
     • F (16) = F (8) * F (8)% Getal1 = 1 * 1% 35 = 1
     • F (32) = F (16) * F (16)% Getal1 = 1 * 1% 35 = 1
   • Bereken gepaarde nummers 1 - 2
     • 35 -2 = 33 (10001) basis 2
     • MMI1 = F (33) = F (32) * F (1) mod 35
     • MMI1 = F (33) = 1 * 27 mod 35
     • MMI1 = 27
   • Voor MMI2
     • F (1) = Getal1% Getal2 = 35% 97 = 35
     • F (2) = F (1) * F (1)% Getal2 = 35 * 35 mod 97 = 61
     • F (4) = F (2) * F (2)% Getal2 = 61 * 61 mod 97 = 35
     • F (8) = F (4) * F (4)% Getal2 = 35 * 35 mod 97 = 61
     • F (16) = F (8) * F (8)% Getal2 = 61 * 61 mod 97 = 35
     • F (32) = F (16) * F (16)% Getal2 = 35 * 35 mod 97 = 61
     • F (64) = F (32) * F (32)% Getal2 = 61 * 61 mod 97 = 35
     • F (128) = F (64) * F (64)% Getal2 = 35 * 35 mod 97 = 61
   • Bereken het gepaarde getal 2 - 2
     • 97 - 2 = 95 = (1011111) basis 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 Bereken (Waarde1 * Getal2 * MMI1 + Waarde2 * Getal1 * MMI2)% (Getal1 * Getal2)
   • Antwoord = (1 * 97 * 27 + 2 * 35 * 61)% (97 * 35)
   • Antwoord = (2619 + 4270)% 3395
   • Antwoord = 99
6. 6 Controleer of Getal1 geen priemgetal is
   • Bereken (Antwoord - Waarde1)% Getal1
   • 99 – 1 % 35 = 28
   • Aangezien 28 groter is dan 0, is 35 geen priemgetal.
7. 7 Controleer of Nummer 2 een priemgetal is.
   • Bereken (Antwoord - Waarde2)% Getal2
   • 99 – 2 % 97 = 0
   • Aangezien 0 0 is, is 97 hoogstwaarschijnlijk een priemgetal.
8. 8 Herhaal stap 1 tot en met 7 nog minstens twee keer.
   • Als u 0 krijgt in stap 7:
     • Gebruik een ander Getal1 als Getal1 geen priemgetal is.
     • Gebruik een ander Getal1 als Getal1 een priemgetal is. In dit geval zou u 0 moeten krijgen in stap 6 en 7.
     • Gebruik verschillende Betekenis1 en Betekenis2.
   • Als je in stap 7 consequent 0 krijgt, dan is nummer 2 zeer waarschijnlijk een priemgetal.
   • Stappen 1 tot en met 7 kunnen een fout opleveren als Getal1 geen priemgetal is en Getal2 een deler is van Getal1. De beschreven methode werkt in alle gevallen wanneer beide getallen priem zijn.
   • De reden dat u stap 1 tot en met 7 moet herhalen, is dat in sommige gevallen, zelfs als Getal1 en Getal 2 geen priemgetal zijn, u in stap 7 0 krijgt (voor een of beide getallen). Dit gebeurt zelden.Kies een ander Getal1 (samengesteld), en als Getal2 geen priemgetal is, dan zal Getal2 niet gelijk zijn aan nul in stap 7 (behalve in het geval dat Getal1 een deler is van Getal2 - hier zullen priemgetallen altijd gelijk zijn aan nul in stap 7).

Tips

• Priemgetallen van 168 tot 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.
• Hoewel testen met brute kracht een vervelende test is bij het werken met grote aantallen, is het behoorlijk efficiënt voor kleine aantallen. Zelfs in het geval van grote getallen, begin met het testen van kleine delers en ga dan verder met meer geavanceerde methoden om de eenvoud van getallen te controleren (als er geen kleine delers worden gevonden).

Wat heb je nodig

• Papier, pen of computer