Controleren of een getal een priemgetal is

Priemgetallen zijn getallen die alleen deelbaar zijn door zichzelf en 1 – andere getallen heten samengestelde getallen. Als het er op aankomt om te testen of een getal een priemgetal is, zijn er verscheidene opties. Sommige van deze methoden zijn relatief eenvoudig maar absoluut niet praktisch voor grotere getallen. Andere tests die vaak worden gebruikt zijn eigenlijk complete algoritmes op basis van een waarschijnlijkheid die soms een getal onterecht als priemgetal aanmerken. Lees verder bij stap 1 om te leren hoe je zelf kunt testen of je te maken hebt met een priemgetal.

Methode 1

Methode 1 van 4:

Proberen door te delen

Pdf downloaden

Proberen door te delen is verreweg de eenvoudigste manier om een getal te testen. Voor kleine getallen is het meestal ook de snelste manier. De test is gebaseerd op de definitie van een priemgetal: een getal is een priemgetal als het alleen maar deelbaar is door zichzelf en 1.

Deel het getal n door alle mogelijke deelbare gehele getallen. Voor grotere getallen zoals n=101, is het enorm onpraktisch om te delen door elk mogelijk gehele getal kleiner dan n. Gelukkig zijn er diverse trucs om het aantal te testen factoren terug te brengen.
2
Bepaal of n even is. Alle even getallen zijn volledig deelbaar door 2. Daarom geldt dat als n even is, je dus kunt zeggen dat n een samengesteld getal is (en dus geen priemgetal). Om snel te bepalen of een getal even is, hoef je alleen op het laatste cijfer te letten. Als het laatste cijfer een 2, 4, 6, 8 of 0 is, dan is het getal even en dus geen priemgetal.
- De enige uitzondering op deze regel is het getal 2 zelf, welke, omdat het deelbaar is door zichzelf en 1, ook een priemgetal is. 2 is het enige even priemgetal.
3
Deel n door elk getal tussen 2 en n-1. Omdat een priemgetal geen andere factoren heeft dan zichzelf en 1 en omdat factoren van gehele getallen kleiner zijn dan hun product, zal het controleren van de deelbaarheid van een geheel getal, kleiner dan n en groter dan 2, bepalen of n een priemgetal is. We beginnen na 2 omdat even getallen (meervouden van 2) geen priemgetallen kunnen zijn. Dit is verre van een efficiënte manier om te testen, zoals je verderop zult zien.
- Bijvoorbeeld, als we deze methode zouden willen gebruiken om te testen of 11 een priemgetal is of niet, dan zouden we 11 moeten delen door 3, 4, 5, 6, 7, 8, 9 en 10, waarbij we elke keer zoeken naar een geheel getal antwoord zonder rest. Omdat geen van deze getallen deel volledig past in 11, kunnen we zeggen dat 11 een priemgetal is.
4
Om tijd te sparen test je alleen tot aan sqrt(n), omhoog afgerond. Het testen van een getal n door alle getallen te controleren tussen 2 en n-1 kan al snel veel tijd gaan kosten. Bijvoorbeeld, als we zouden willen controleren of 103 een priemgetal is met deze methode, dan zouden we moeten delen door 3, 4, 5, 6, 7 ... enz., helemaal tot aan 102! Gelukkig is het niet nodig om zo te testen. In de praktijk is het alleen nodig om te testen door de factoren tussen 2 en de vierkantswortel van n. Als de vierkantswortel van n geen getal is, rond deze dan af naar het dichtstbijzijnde gehele getal en test tot aan dit getal. Zie hieronder voor een uitleg:
- Laten we de factoren van 100 eens onderzoeken. 100 = 1 × 100, 2 × 50, 4 × 25, 5 × 20, 10 × 10, 20 × 5, 25 × 4, 50 × 2 en 100 × 1. Merk op dat na 10 × 10, de factoren hetzelfde zijn als die voor 10 × 10, alleen dan omgedraaid. Over het algemeen kunnen we de factoren van n groter dan sqrt(n) negeren, omdat ze gewoon een voortzetting zijn van factoren kleiner dan sqrt(n).
- Laten we een voorbeeld proberen. Als n = 37, dan hoeven we niet alle getallen van 3 tot en met 36 te testen, om te bepalen of n een priemgetal is. In plaats daarvan hoeven we alleen de getallen tussen 2 en sqrt(37) (omhoog afgerond) te bekijken.
  - sqrt(37) = 6.08 – we gaan dit omhoog afronden naar 7.
  - 37 is niet volledig deelbaar door 3, 4, 5, 6,en 7 en dus kunnen we met vertrouwen stellen dat het een priemgetal is.
5
Om nog meer tijd uit te sparen, gebruiken we alleen priemfactoren. Het is mogelijk om het proces van testen door delen nog korter te maken door die factoren niet mee te nemen die geen priemgetallen zijn. Per definitie is het zo dat elk samengesteld getal uit te drukken is als het product van twee of meer priemgetallen. Dus het delen van het getal n door een samengesteld getal is overbodig – dit is gelijk aan het meerdere malen delen door priemgetallen. Dus, kunnen we de lijst met mogelijke factoren verder uitdunnen tot alleen priemgetallen kleiner dan sqrt(n).
- Dit houdt in dat alle even factoren, zowel als de factoren die meervouden zijn van priemgetallen, kunnen worden overgeslagen.
- Bijvoorbeeld, laten we proberen vast te stellen of 103 een priemgetal is of niet. De vierkantswortel van 103 is 11 (omhoog afgerond). De priemgetallen tussen 2 en 11 zijn 3, 5, 7 en 11. 4, 6, 8 en 10 zijn even en 9 is een veelvoud van 3, een priemgetal, dus kunnen we deze overslaan. Door dit te doen hebben we onze lijst met mogelijke factoren teruggebracht tot slechts 4 getallen!
  - 103 is zowel door 3, 5, 7 of 11 niet volledig deelbaar, dus weten we nu dat 103 een priemgetal is.
Advertentie

Methode 2

Methode 2 van 4:

Met behulp van de kleine stelling van Fermat

Pdf downloaden

In 1640 heeft de Franse wiskundige Pierre de Fermat voor het eerst een stelling geponeerd (welke nu naar hem is vernoemd) die zeer behulpzaam kan zijn bij het bepalen of een getal wel of niet een priemgetal is. Technisch gezien is de test van Fermat bedoeld om na te gaan om een getal samengesteld is, in plaats van een priemgetal. Dit omdat de test met "absolute zekerheid" kan aantonen dat een getal samengesteld is, maar alleen een "waarschijnlijkheid" of een getal een priemgetal is.^[1]XBron De kleine stelling van Fermat is bruikbaar in situaties waarbij proberen door te delen niet praktisch is en wanneer er een lijst met getallen beschikbaar is die uitzonderingen zijn op de stelling.

Deze test gebruik je om te bepalen of een gegeven getal n een priemgetal is. Maar zoals al hierboven aangegeven, kan deze stelling af en toe bepaalde samengestelde foutief kenmerken als priemgetal. Het is belangrijk hiermee rekening te houden en je antwoord te controleren, iets wat verderop wordt uitgelegd.
2
Kies een geheel getal a tussen 2 en n-1 (inclusief). Het exacte gehele getal dat je kiest is niet belangrijk. Omdat de parameters voor a inclusief 2 en n-1 zijn, kun je deze ook gebruiken.
- Een voorbeeld: Is 100 wel of niet een priemgetal. Stel we nemen 3 als testwaarde - dit ligt tussen 2 en n-1, dus dat voldoet.
3
Bereken aⁿ (mod n). Het uitwerken van deze uitdrukking vereist wat kennis van een wiskundig systeem genaamd modulaire wiskunde. In de modulaire wiskunde keren getallen terug naar nul bij het bereiken van een bepaalde waarde, ook wel de modulus. Je kunt hierover denken als een klok: uiteindelijk zal de wijzer van de klok na 12 uur weer terugschieten naar 1 uur, niet naar 13 uur. De modulus wordt genoteerd als (mod n). Dus bij deze stap bereken je aⁿ met een modulus van n.
- Een andere methode is het uitrekenen van aⁿ, en daarna dit delen door n, waarna je de rest gebruikt als je antwoord. Gespecialiseerde rekenmachines met een modulus functie^[2]XBron kunnen bij een deling van grote getallen zeer van pas komen, omdat deze direct de rest van een deling uit kunnen rekenen.
- Als we een dergelijke rekenmachine gebruiken bij ons voorbeeld, dan kunnen we zien dat 3¹⁰⁰/100 een rest heeft van 1. Dus, 3¹⁰⁰ (mod 100) is 1.
4
Als we dit met de hand uitrekenen, dan gebruiken we de exponent als korte notatie. Heb je geen rekenmachine met een modulus functie, gebruik dan de notatie met een exponent om de procedure van het bepalen van de rest gemakkelijker te maken. Zie hieronder:
- In ons voorbeeld berekenen we 3¹⁰⁰ met een modulus van 100. 3¹⁰⁰ is een heel erg groot getal - 515,377,520,732,011,331,036,461,129,765,621,272,702,107,522,001 – zo groot dat het erg moeilijk wordt om mee te werken. Liever dan het 48-cijferige antwoord te gebruiken voor 3¹⁰⁰, kunnen we het beter noteren als exponent, dus (((((((3²)*3)²)²)²)*3)²)². Onthoud dat het nemen van de exponent van een exponent het effect geeft van het vermenigvuldigen van de exponenten ((x^y)^z = x^yz).
  - Nu kunnen we de rest gaan bepalen. Begin met het oplossen van (((((((3²)*3)²)²)²)*3)²)² bij de binnenste set haakjes en werk zo verder naar buiten, waarbij je elke stap door 100 deelt. Hebben we de rest gevonden, dan gebruiken we dat voor de volgende stap in plaats van als het daadwerkelijke antwoord. Zie hieronder:
    - (((((((9)*3)²)²)²)*3)²)² - 9/100 heeft geen rest, dus kunnen we verder gaan.
    - ((((((27)²)²)²)*3)²)² - 27/100 heeft geen rest, dus kunnen we verder gaan.
    - (((((729)²)²)*3)²)² - 729/100 = 7 R 29. Onze rest is 29. We gaan verder met de volgende stap, en niet met 729.
    - ((((29²=841)²)*3)²)² - 841/100 = 8 R 41. We gebruiken onze rest 41 nogmaals in de volgende stap.
    - (((41² = 1681)*3)²)² - 1681/100 = 16 R 81. We gebruiken onze rest 81 in de volgende stap.
    - ((81*3 = 243)²)² - 243/100 = 2 R 43. We gebruiken onze rest 43 in de volgende stap.
    - (43² = 1849)² - 1849/100 = 18 R 49. We gebruiken onze rest 49 in de volgende stap.
    - 49² = 2401 - 2401/100 = 24 R 1. ons uiteindelijke rest is 1. Met andere woorden, 3¹⁰⁰ (mod 100) = 1. Merk op dat dit hetzelfde antwoord is als welke we berekend hebben in de vorige stap!
5
Ga na of aⁿ (mod n) = a (mod n). Zo niet, dan is n samengesteld. Indien waar, dan is n waarschijnlijk, (maar niet zeker) een priemgetal. Het herhalen van de test met verschillende waarden voor a kan de uitkomst zekerder maken, maar er zijn zeldzame samengestelde getallen die voldoen aan de stelling van Fermat voor alle waarden van a. Deze heten de Carmichael getallen - de kleinste van deze getallen is 561.
- In ons voorbeeld, 3¹⁰⁰ (mod 100) = 1 en 3 (mod 100) = 3. 1 ≠ 3, dus kunnen we stellen dan 100 een samengesteld getal is.
6
Gebruik de Carmichael getallen om zeker te zijn van je uitkomst. Weten welke getallen voldoen aan de Carmichael-reeks voor je verder gaat, kan je veel hoofdbrekens schelen over de vraag of een getal wel of niet een priemgetal is. Over het algemeen zijn Carmichael getallen het product van afzonderlijke priemgetallen, waarbij voor alle priemgetallen geldt dat als p een deler is van n, dat ook p-1 een deler is van n-1.^[3]XBron De online lijst met Carmichael getallen kan zeer handig zijn om, met behulp van De kleine stelling van Fermat, te bepalen of een getal een priemgetal is.

Advertentie

Methode 3

Methode 3 van 4:

Met behulp van de Miller-Rabin Test

Pdf downloaden

De Miller-Rabin test werkt op dezelfde manier als de kleine stelling van Fermat, maar gaat op een betere manier om met afwijkende getallen zoals Carmichael-getallen.^[4]XBron

Zoals in de hierboven aangegeven methoden is n de variabele waar we de primaliteit van willen bepalen.
2
Druk n-1 uit in de vorm 2^s × d waarbij d oneven is. Het getal n is een priemgetal als het oneven is. Dus n - 1 moet dan even zijn. Omdat n - 1 even is, kan het worden geschreven als een macht van 2 maal een oneven getal . Dus, 4 = 2² × 1; 80 = 2⁴ × 5; enzovoort.
- Stel we willen bepalen of n = 321 een priemgetal is. 321 - 1 = 320, wat we kunnen uitdrukken als 2⁶ × 5.
  - In dit geval is n = 321 een geschikt getal. n – 1 bepalen voor n = 371 kan een grote waarde vereisen voor d, wat het hele proces in een later stadium moeilijker maakt. 371 - 1 = 370 = 2¹ × 185
3
Kies een willekeurig getal a tussen 2 en n-1. Het exacte getal wat je kiest is niet van belang – alleen maar dat het kleiner moet zijn dan n en groter dan 1.
- In ons voorbeeld met n = 321, kiezen we a = 100.
4
Bereken a^d (mod n). Als a^d = 1 of -1 (mod n), dan doorstaat n de Miller-Rabin test en is waarschijnlijk een priemgetal. Evenals bij de Kleine stelling van Fermat, kan deze test niet met absolute zekerheid de primaliteit van een getal vaststellen, maar heeft daarvoor aanvullende tests nodig.
- In ons voorbeeld met n = 321, a^d (mod n) = 100⁵ (mod 321). 100⁵ = 10,000,000,000 (mod 321) = 313. We gebruiken hiervoor een speciale rekenmachine, of de verkorte methode met een exponent zoals eerder beschreven, om de rest te vinden van 100⁵/321.
  - Omdat we geen 1 of -1 hebben verkregen, kunnen we niet met zekerheid zeggen dat n een priemgetal. Maar er is nog meer dat we moeten doen – lees verder.
5
Omdat het resultaat niet gelijk is aan 1 of -1, bereken dan a^2d, a^4d, ... enzovoort, tot aan a^{2^s-1d}. Bereken a tot de macht van d maal , tot aan 2^s-1. Als één van deze gelijk is aan 1 of -1 (mod n), dan doorstaat n de Miller-Rabin test en is waarschijnlijk een priemgetal. Als je hebt bepaald dat n voldoet aan de test, controleer vervolgens je antwoord (zie de stap hieronder). Als n niet voldoet aan één van deze tests, dan is het een samengesteld getal.
- Ter herinnering: in ons voorbeeld is de waarde van a gelijk aan 100, de waarde van s is 6, en van d 5. We gaan verder met testen zoals hieronder aangegeven:
  - 100^{2d = 10} = 1 × 10²⁰.
    - 1 × 10²⁰ (mod 321) = 64. 64 ≠' 1 or -1. Rustig door blijven gaan.
  - 100^{4d = 20} = 1 × 10⁴⁰.
    - 1 × 10⁴⁰ (mod 321) = 244. 244 ≠ 1 or -1.
  - Op dit punt aangekomen kunnen we stoppen. s - 1 = 6 - 1 = 5. We hebben nu 4d = 2² bereikt, en er zijn geen machten van 2 maal d onder 5d. Omdat geen enkele van onze berekeningen een 1 of -1 als antwoord hebben gegeven, kunnen we stellen dat n = 321 een samengesteld getal is.
Als je hebt gevonden dat de waarde van n wel eens een priemgetal kan zijn, probeer het dan nogmaals met een andere, willekeurige waarde voor a om de uitkomst van de test te bevestigen. Als n daadwerkelijk een priemgetal is, dan zal dit kloppen voor elke waarde van a. Als n een samengesteld getal is, dan zal het falen voor driekwart van de waarden van a. Hiermee heb je meer zekerheid dan met de Kleine stelling van Fermat, waarbij bepaalde samengestelde getallen (de Carmichael getallen) de test doorstaan voor elke waarde van a.
Advertentie

Methode 4

Methode 4 van 4:

Met behulp van de Chinese reststelling

Pdf downloaden

1
Kies twee getallen. Een van de getallen is geen priemgetal en de tweede is het getal welke op primaliteit wordt getest.
- "Testgetal1" = 35
- Testgetal2 = 97
2
Kies twee gegevenspunten groter dan nul en kleiner dan Testgetal1 respectievelijk Testgetal2. Ze mogen niet gelijk zijn aan elkaar.
- Data1 = 1
- Data2 = 2
3
Bereken de MMI (Mathematical Multiplicative Inverse) voor Testgetal1 en Testgetal2
- Bereken de MMI
  - MMI1 = Testgetal2 ^ -1 Mod Testgetal1
  - MMI2 = Testgetal1 ^ -1 Mod Testgetal2
- Alleen voor priemgetallen (er zal een uitkomst zijn voor niet-priemgetallen, maar dat is niet de MMI):
  - MMI1 = (Testgetal2 ^ (Testgetal1-2)) % Testgetal1
  - MMI2 = (Testgetal1 ^ (Testgetal-2)) % Testgetal2
- Dus:
  - MMI1 = (97 ^ 33) % 35
  - MMI2 = (35 ^ 95) % 97
4
Maak een binaire tabel voor elke MMI tot aan Log2 van de Modulus
- For de MMI1
  - F(1) = Testgetal2 % Testgetal1 = 97 % 35 = 27
  - F(2) = F(1) * F(1) % Testgetal1 = 27 * 27 % 35 = 29
  - F(4) = F(2) * F(2) % Testgetal1 = 29 * 29 % 35 = 1
  - F(8) = F(4) * F(4) % Testgetal1 = 1 * 1 % 35 = 1
  - F(16) =F(8) * F(8) % Testgetal1 = 1 * 1 % 35 = 1
  - F(32) =F(16) * F(16) % Testgetal1 = 1 * 1 % 35 = 1
- Bereken de binaire logaritme van Testgetal1 - 2
  - 35 -2 = 33 (10001) grondtal 2
  - MMI1 = F(33) = F(32) * F(1) mod 35
  - MMI1 = F(33) = 1 * 27 Mod 35
  - MMI1 = 27
- For MMI2
  - F(1) = Testgetal1 % Testgetal2 = 35 % 97 = 35
  - F(2) = F(1) * F(1) % Testgetal2 = 35 * 35 mod 97 = 61
  - F(4) = F(2) * F(2) % Testgetal2 = 61 * 61 mod 97 = 35
  - F(8) = F(4) * F(4) % Testgetal2 = 35 * 35 mod 97 = 61
  - F(16) = F(8) * F(8) % Testgetal2 = 61 * 61 mod 97 = 35
  - F(32) = F(16) * F(16) % Testgetal2 = 35 * 35 mod 97 = 61
  - F(64) = F(32) * F(32) % Testgetal2 = 61 * 61 mod 97 = 35
  - F(128) = F(64) * F(64) % Testgetal2 = 35 * 35 mod 97 = 61
- Bereken de binaire logaritme van Testgetal2 - 2
  - 97 - 2 = 95 = (1011111) grondtal 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
Bereken (Data1 * Testgetal2 * MMI1 + Data2 * Testgetal1 * MMI2) % (Testgetal1 * Testgetal)
- Antwoord = (1 * 97 * 27 + 2 * 35 * 61) % (97 * 35)
- Antwoord = (2619 + 4270) % 3395
- Antwoord = 99
6
Controleer of "Testgetal1" geen priemgetal1 is
- Bereken (Antwoord - Data1) % Testgetal1
- 99 -1 % 35 = 28
- Omdat 28 groter is dan 0, is 35 geen priemgetal
7
Ga na of Testgetal2 een priemgetal is
- Bereken (Antwoord - Data2) % Testgetal2
- 99 - 2 % 97 = 0
- Omdat 0 gelijk is aan 0, is 97 een potentieel primegetal
8
Herhaal de stappen 1 tot en met 7 tenminste nog tweemaal.
- Als stap 7 gelijk is 0:
  - Gebruik een ander "Testgetal1" als Testgetal1 geen priemgetal is.
  - Gebruik een ander Testgetal1 waarbij een Testgetal1 daadwerkelijk een priemgetal is. In dit geval zijn de stappen 6 en 7 gelijk aan 0.
  - Gebruik verschillende gegevenspunten voor data1 en data2.
- Als stap 7 steeds gelijk is aan 0, dan is de kans dat getal2 een priemgetal is, zeer groot.
- De stappen 1 tot en met 7 staan erom bekend dat ze in bepaalde gevallen niet kloppen wanneer het eerste getal geen priemgetal is en de tweede een priemfactor van het niet-priemgetal "Testgetal1". Het werkt in alle scenario's waarvan bij beide getallen priemgetallen zijn.
- De reden dat de stappen 1 tot en met 7 worden herhaald, is omdat er een paar scenario's zijn waarbij, zelfs als Testgetal1 geen priemgetal is en Testgetal2 geen priemgetal, een van beide getallen van stap 7 nog steeds nul is. Deze omstandigheden zijn zeldzaam. Door het veranderen van Testgetal1 in een ander niet-priemgetal, als Testgetal2 geen priemgetal is, zal Testgetal2 niet meer gelijk zijn aan nul, in stap 7. Met uitzondering van het geval waarbij "Testgetal1" een factor is van Testgetal2, zullen priemgetallen altijd nul zijn in stap 7.
Advertentie

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 ^[5]XBron
Wanneer het proberen door te delen langzamer is dan de meer verfijnde methoden, dan is het nog steeds efficiënt voor kleinere getallen. Zelfs bij het testen van grotere getallen is het niet ongewoon om eerst de kleine getallen te controleren, voor je overschakelt op de meer geavanceerde methoden.

Advertentie