Priemgetal | natuurlijk getal van een bepaalde soort

Er is een eenvoudige methode om een lijst van priemgetallen te vinden. Eratosthenes heeft die bedacht. Het heeft de naam Zeef van Eratosthenes. Het vangt getallen op die niet priem zijn (zoals een zeef), en laat de priemgetallen door.

De methode werkt met een lijst getallen, en een speciaal getal, b genaamd, dat tijdens de methode verandert. Terwijl men de methode doorloopt, omcirkelt men sommige getallen in de lijst en streept andere door. Elk omcirkeld getal is een priemgetal en elk doorgestreept getal is samengesteld. In het begin zijn alle getallen gewoon: niet omcirkeld en niet doorgestreept.

De methode is altijd dezelfde:

1. Schrijf op een vel papier alle gehele getallen van 2 tot en met het getal dat wordt getest. Schrijf het getal 1 niet op. Ga naar de volgende stap.
2. Begin met b gelijk aan 2. Ga naar de volgende stap.
3. Omcirkel b in de lijst. Ga naar de volgende stap.
4. Begin bij b, tel nog eens b op in de lijst en streep dat getal door. Herhaal dit tot het einde van de lijst. Ga naar de volgende stap.
• (Bijvoorbeeld: Als b 2 is, omcirkelt u 2 en streept u 4, 6, 8, enzovoort door. Als b gelijk is aan 3, omcirkelt u 3 en streept u 6, 9, 12, enzovoort door. 6 en 12 zijn al doorgestreept. Streep ze opnieuw door).
5. Verhoog b met 1. Ga naar de volgende stap.
6. Als b is doorgestreept, ga dan terug naar de vorige stap. Als b een getal in de lijst is dat niet is doorgestreept, ga dan naar de 3e stap. Als b niet in de lijst voorkomt, ga dan naar de laatste stap.
7. (Dit is de laatste stap.) U bent klaar. Alle priemgetallen zijn omcirkeld en alle samengestelde getallen zijn doorgestreept.

Men kan deze methode bijvoorbeeld toepassen op een lijst met getallen van 2 tot 10. Uiteindelijk zullen de getallen 2, 3, 5 en 7 omcirkeld zijn. Dit zijn priemgetallen. De getallen 4, 6, 8, 9 en 10 worden doorgestreept. Dit zijn samengestelde getallen.

Deze methode of dit algoritme duurt te lang om zeer grote priemgetallen te vinden. Ze is echter minder ingewikkeld dan methoden die worden gebruikt voor zeer grote priemgetallen, zoals de primaliteitstest van Fermat (een test om te zien of een getal al dan niet priem is) en de Miller-Rabin primaliteitstest.

Priemgetallen zijn zeer belangrijk in de wiskunde en de informatica. Zeer lange getallen zijn moeilijk op te lossen. Het is moeilijk om hun priemfactoren te vinden, dus meestal worden getallen die waarschijnlijk priem zijn gebruikt voor encryptie en geheime codes. Bijvoorbeeld:

• De meeste mensen hebben een bankkaart, waarmee ze via een geldautomaat geld van hun rekening kunnen halen. Deze kaart wordt beschermd door een geheime toegangscode. Omdat de code geheim moet blijven, kan hij niet in cleartext op de kaart worden opgeslagen. Er wordt encryptie gebruikt om de code op een geheime manier op te slaan. Deze versleuteling maakt gebruik van vermenigvuldigingen, delingen en het vinden van resten van grote priemgetallen. In de praktijk wordt vaak een algoritme gebruikt dat RSA heet. Het maakt gebruik van het Chinese restanttheorema.

• Als iemand een digitale handtekening voor zijn e-mail heeft, wordt encryptie gebruikt. Dit zorgt ervoor dat niemand een e-mail van hem of haar kan vervalsen. Voor de ondertekening wordt een hashwaarde van het bericht gecreëerd. Deze wordt vervolgens gecombineerd met een digitale handtekening om een ondertekend bericht te produceren. De gebruikte methoden zijn min of meer dezelfde als in het eerste geval hierboven.

• Het vinden van het grootste bekende priemgetal is in de loop der jaren een soort sport geworden. Testen of een getal priem is, kan moeilijk zijn als het getal groot is. De grootste priemgetallen die op enig moment bekend zijn, zijn meestal Mersenne-priemgetallen, omdat de snelst bekende test voor primaliteit de Lucas-Lehmer-test is, die gebaseerd is op de speciale vorm van Mersenne-getallen.

• Coprime
• Lijst van priemgetallen
• Palindroompriem
• Prime factorisatie
• Wilson prime