WisFaq!

Het vinden van priemgetallen

Om priemgetallen te berekenen bestaat de manier van eratosthenes, het wegstrepen van 1 en getallen die te delen zijn door 2 en 3, maar bestaan er ook andere manieren om te kijken of een getal een priemgetal is?

eva
31-1-2003

Antwoord

Er zijn heel wat manieren om priemgetallen te vinden. Ik zal er hier een aantal opnoemen. Het zou te veel zijn om al deze manieren ook hier uit te leggen, maar als je meer wilt weten over dit onderwerp geeft het je wel nieuwe onderwerpen om op internet of in de bibliotheek verder te zoeken.

Priemgetallen door deling
Elk samengesteld getal $n>1$ heeft tenminste 1 priemdeler kleiner of gelijk aan $\sqrt{n}$.

Dat betekent ook dat als je een willekeurig getal n hebt en je kunt geen delers vinden kleiner of gelijk aan $\sqrt{n}$ dat dit getal een priemgetal is.

Dit wetende kun je makkelijk een manier verzinnen om priemgetallen te vinden.

Stel je wilt de priemgetallen tot en met 100 weten. Je hoeft dan alleen maar naar de oneven getallen te kijken, want we weten al dat er maar een even priemgetal is: 2.

Je kunt dan elk oneven getal tot 100 delen door alle oneven getallen kleiner dat de wortel van dat getal.

Als je het wat slimmer aanpakt en het lijstje afgaat en ondertussen de priemgetallen opschrijft, hoef je elk getal alleen maar proberen te delen door de priemgetallen kleiner dat de wortel van het getal:

     2: priem
     3: priem
     5: niet deelbaar door 3 dus priem
     7: niet deelbaar door 3 dus priem
     9: deelbaar door 3
    11: niet deelbaar door 3 dus priem
    13: niet deelbaar door 3 dus priem
    15: deelbaar door 3
    17: niet deelbaar door 3 dus priem
    19: niet deelbaar door 3 dus priem
    21: deelbaar door 3
    23: niet deelbaar door 3 dus priem
    25: niet deelbaar door 3; deelbaar door 5
    ................

De zeef van Eratosthenes

Dat is de manier die je al beschreef hierboven.

Het vinden van willekeurige grote priemgetallen

In bijvoorbeeld de cryptografie wordt met hele grote priemgetallen gewerkt. Deze getallen moeten willekeurig zijn, dus kunnen niet op de hierboven beschreven manieren worden gevonden.

De algemenen manier is dat er een willekeurig oneven getal wordt gekozen en dat dan met een priemgetal test wordt gekeken of dit getal een priemgetal is. Zo niet, dan wordt er weer een nieuw getal gekozen en dan begint het weer opnieuw.

Die priemgetal testen kun je in twee soorten onderverdelen.

'(True) primality tests'
'Probabilistic primality tests'

De eerste soort zijn testen waarbij het zeker is dat een getal priem is als dat uit de test komt. Voorbeelden hiervan zijn de Lucas-Lehmer test voor Mersenne getallen en de Maurer test.

Voor een aantal toepassingen is het voldoende als het willekeurige getal waarschijnlijk priem is.

Bij de 'Probabilistic primality tests' zijn de getallen die aangemerkt worden als samengesteld zeker samengesteld, maar er bestaan samengestelde getallen die goed door de test komen. Geeft de test niet aan dat een getal samengesteld is, dan is die met grote waarschijnlijkheid priem, maar met een kleine kans zou het een samengesteld getal kunnen zijn.

Voorbeelden van deze soort test zijn:
Fermat's test, Solovay-Strassen en Miller-Rabin.

Vaak worden deze testen gecombineerd met het delen door de kleine priemgetallen. Zo zou het willekeurig gekozen getal, eerst door de eerste 100 priemgetallen gedeeld kunnen worden en als het getal daar niet deelbaar door is pas aan een test onderworpen kunnen worden. Het delen door de eerste 100 priemgetallen kost relatief weinig tijd en filtert al veel samengestelde getallen uit de willekeurig gekozen getallen.

Fermat's test

Fermat's test is gebaseerd op het gegeven dat voor een priemgetal p geldt:

a^p-1 $\equiv$ 1 mod p

Fermat's test bestaat er dan ook uit een aantal basis a te kiezen en te controleren of het aan bovenstaande eigenschap voldoet. Zo niet dan is het getal zeker geen priem.

Veel plezier!

gm
1-2-2003