Inhoud

• Stappen
• Tips
• Benodigde materialen

Priemgetallen kunnen alleen worden gedeeld door 1 en door zichzelf. Alle andere nummers worden verbindingen genoemd. Er zijn verschillende manieren om te weten of een getal een priemgetal is of niet, maar er wordt een prijs voor betaald. Enerzijds zijn sommige tests perfect, maar te traag voor grote getallen. Aan de andere kant zijn er snellere tests die valse resultaten kunnen geven. Hier zijn enkele opties waaruit u kunt kiezen, afhankelijk van de grootte van het nummer dat u test.

Stappen

Deel 1 van 3: testen

Notitie: in alle formules,n is het nummer dat wordt getest.

1. 

   Proef split-test: schuld n door de priemgetallen van twee tot het plafond ().

2. 

   
   
   Kleine stelling van Fermat. Waarschuwing: het kan valse positieven genereren, zelfs voor alle waarden van een.
   • Kies een geheel getal voor De, zoals 2 ≤ tot ≤ n - 1.
   • Als a (mod n) = a (mod n), dan is n waarschijnlijk een priemgetal. Als dit niet waar is, is n geen neef.
   • Herhaal met verschillende waarden van De om het vertrouwen in het resultaat te vergroten.

3. 

   
   
   Miller-Rabin-test. Waarschuwing: false positives zijn mogelijk, maar zeldzaam voor verschillende waarden van een.
   • Vind waarden voor s en d zodanig dat.
   • Kies een geheel getal voor De, zoals 2 ≤ tot ≤ n - 1.
   • Als a = +1 (mod n) of -1 (mod n), is n waarschijnlijk een priemgetal. Ga naar het testresultaat of ga verder met de volgende stap.
   • Maak het resultaat vierkant (). Als het gelijk is aan +1 (mod n) of -1 (mod n), ga dan naar het testresultaat. Herhaal anders (etc.) tot
   • Testresultaat: als n de test doorstaat, herhaal dan met verschillende waarden van De om het resultaat te bevestigen.

Deel 2 van 3: De priemgetal-test begrijpen

1. 

   
   
   Begrijp de voorlopige verdelingsmethode. Per definitie, n het is alleen een priemgetal als het niet gelijkelijk kan worden gedeeld door hele getallen groter dan 2. Deze formule bespaart tijd door onnodige tests te verwijderen (bijv. na test 3 is het niet nodig om 9 te testen).
   • Plafond (x) rondt x af naar het volgende gehele getal ≥ x.

2. 

   Begrijp modulaire rekenkunde. De bewerking "x mod y" (afkorting van "module") betekent "deel x door y en vind de rest". Met andere woorden, in modulaire rekenkunde gaan getallen terug naar nul nadat ze een bepaalde waarde hebben bereikt, genaamd module. De klok telt in module 12: hij gaat van 10 naar 11 en dan naar 12. Daarna gaat hij terug naar 1.
   • Verschillende rekenmachines hebben een mod-knop, maar lees het einde van dit deel om te leren hoe je met de hand kunt oplossen bij grote getallen.

3. 

   Ken de valkuilen van de kleine stelling van Fermat. Alle getallen die niet slagen voor deze test zijn verzonnen (geen priemgetallen), maar helaas zijn de getallen die slagen juist waarschijnlijk nichten en neven. Als u zeker wilt zijn dat u valse positieven vermijdt, zoekt u naar de n in een lijst met 'Carmichael-nummers' (die altijd slagen voor deze test) en 'Fermat pseudo-neven' (die alleen voor deze test slagen voor sommige waarden van De.

4. 

   Gebruik waar mogelijk de Miller-Rabin-test. Hoewel het saai is om met de hand te maken, wordt het veel gebruikt in computerprogramma's. Het kan met een praktische snelheid worden uitgevoerd en geeft minder valse positieven dan de Fermat-methode. Een samengesteld getal geeft nooit een vals positief resultaat voor meer dan 1/4 van de De. Als u meerdere willekeurige waarden van De en ze slagen allemaal voor de test, daar kunt u op vertrouwen n is een neef.

5. 

   Voer modulaire berekeningen uit voor grote getallen. Als je geen rekenmachine hebt met de mod-functie, of als de jouwe zulke hoge getallen niet kan weergeven, gebruik dan de exponenteigenschappen en modulaire rekenkunde om het proces gemakkelijker te maken. Hier is een voorbeeld voor mod 50:
   • Herschrijf de uitdrukking met exponenten die gemakkelijker zijn om mee om te gaan: mod 50. (Mogelijk moet u deze verder ontleden als u met de hand berekent).
   • mod 50 = mod 50 mod 50) mod 50. (Dit is een eigenschap van modulaire vermenigvuldiging).
   • mod 50 = 43.
   • mod 50 mod 50) mod 50 = mod 50
   • mod 50

Deel 3 van 3: Chinese Rest Theorem Test

1. 

   Kies twee cijfers. Een van de cijfers is geen priemgetal en de tweede is wat moet worden getest.
   • Primo1 = 35
   • Primo2 = 97

2. 

   Kies twee gegevenspunten groter dan nul en kleiner dan Primo1 en Primo2, respectievelijk. Ze kunnen niet hetzelfde zijn.
   • Gegevens1 = 1
   • Gegevens2 = 2

3. 

   Bereken de multiplicatieve inverse (IM) van Primo1 en Primo2.
   • Bereken de IM
     • IM1 = Primo2 ^ -1 Mod Primo1
     • IM2 = Primo1 ^ -1 Mod Primo2
   • Alleen voor priemgetallen (geeft een getal voor niet-priemgetallen, maar het zal niet hun IM zijn):
     • IM1 = (Primo2 ^ (Primo1-2))% Primo1
     • IM2 = (Primo1 ^ (Primo2-2))% Primo2
   • Ex.:
     • IM1 = (97 ^ 33)% 35
     • IM2 = (35 ^ 95)% 97

4. 

   Maak een binaire tabel voor elke IM tot aan Log2 van de module.
   • Voor de IM1
     • F (1) = Primo2% Primo1 = 97% 35 = 27
     • F (2) = F (1) * F (1)% Primo1 = 27 * 27% 35 = 29
     • F (4) = F (2) * F (2)% Primo1 = 29 * 29% 35 = 1
     • F (8) = F (4) * F (4)% Prime 1 = 1 * 1% 35 = 1
     • F (16) = F (8) * F (8)% Prime 1 = 1 * 1% 35 = 1
     • F (32) = F (16) * F (16)% Primo1 = 1 * 1% 35 = 1
   • Bereken het koppel van Primo1 - 2
     • 35-2 = 33 (10001) basis 2
     • IM1 = F (33) = F (32) * F (1) mod 35
     • IM1 = F (33) = 1 * 27 Mod 35
     • IM1 = 27
   • Voor MMI2
     • F (1) = Prime 1% Prime 2 = 35% 97 = 35
     • F (2) = F (1) * F (1)% Primo2 = 35 * 35 mod 97 = 61
     • F (4) = F (2) * F (2)% Primo2 = 61 * 61 mod 97 = 35
     • F (8) = F (4) * F (4)% Primo2 = 35 * 35 mod 97 = 61
     • F (16) = F (8) * F (8)% Primo2 = 61 * 61 mod 97 = 35
     • F (32) = F (16) * F (16)% Primo2 = 35 * 35 mod 97 = 61
     • F (64) = F (32) * F (32)% Primo2 = 61 * 61 mod 97 = 35
     • F (128) = F (64) * F (64)% Primo2 = 35 * 35 mod 97 = 61
   • Bereken het koppel van Primo2 - 2
     • 97 - 2 = 95 = (1011111) grondtal 2
     • IM2 = ((((((F (64) * F (16)% 97) * F (8)% 97) * F (4)% 97) * F (2)% 97) * F (1)% 97)
     • IM2 = (((((((35 * 35)% 97) * 61)% 97) * 35% 97) * 61% 97) * 35% 97)
     • IM2 = 61

5. 

   Bereken (Data1 * Primo2 * MMI1 + Data2 * Primo1 * IM2)% (Primo1 * Primo2)
   • Antwoord = (1 * 97 * 27 + 2 * 35 * 61)% (97 * 35)
   • Antwoord = (2619 + 4270)% 3395
   • Antwoord = 99

6. 

   Bevestig dat "Primo1" geen neef is.
   • Bereken (Antwoord - Gegevens1)% Primo1
   • 99 -1 % 35 = 28
   • Omdat 28 groter is dan 0, is 35 geen priemgetal.

7. 

   Kijk of Primo2 een neef is.
   • Bereken (Antwoord - Gegevens2)% Primo2
   • 99 - 2 % 97 = 0
   • Omdat 0 gelijk is aan 0, is 97 mogelijk een priemgetal.

8. 

   Herhaal stap 1 tot en met 7 nog minstens twee keer.
   • Als stap 7 0 is:
     • Gebruik een andere "Primo1" die geen neef is
     • Gebruik een andere Primo1 die een neef is. In dit geval moeten stappen 6 en 7 0 zijn.
     • Gebruik verschillende datapunten voor Data1 en Data2.
   • Als stap 7 elke keer 0 geeft, is de kans dat Primo2 een priemgetal is erg groot.
   • Stappen 1 tot 7 mislukken in bepaalde gevallen, wanneer het eerste getal geen priemgetal is en het tweede een factor van het eerste is. Ze werken in alle scenario's waarin de twee cijfers een priemgetal zijn.
   • De reden dat stap 1 tot en met 7 worden herhaald, is omdat er enkele gevallen zijn waarin, hoewel Primo1 en Primo 2 geen priemgetallen zijn, stap 7 nog steeds nul geeft aan een of beide getallen. Deze gebeurtenis is zeldzaam. Als je Primo1 ruilt voor een ander niet-priemgetal en Primo2 is geen priemgetal, dan zal het in stap 7 niet langer 0 opleveren. Behalve als Primo1 bijvoorbeeld een factor is van Primo2. In dit geval geven priemgetallen altijd 0 in stap 7.

Tips

• De 168 priemgetallen onder de 1000 zijn: 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 de voorzichtige deelmethode langzamer is dan de meer geavanceerde methode voor grotere getallen, is deze nog steeds behoorlijk efficiënt voor kleinere getallen. Zelfs bij het testen van grote aantallen is het niet ongebruikelijk om eerst naar kleine factoren te zoeken voordat u overschakelt op een meer geavanceerde methode wanneer deze niet worden gevonden.

Benodigde materialen

• Hulpmiddelen, zoals potlood en papier of een computer