Inleiding
In deze aflevering gaan we naar priemgetallen kijken. Priemgetallen behoorden tot halverwege de vorige eeuw tot het gebied van de zuivere wiskunde. Met de intreding van de computer en het informatietijdperk, veranderde dit echter. Heden ten dagen vormen priemgetallen de belangrijkste soort getallen die we kennen. Dit komt omdat ze eigenschappen bezitten die gebruikt worden in de cryptografie, ofwel de versleuteling van informatie. Nadat ik de definitie met wat voorbeelden heb gegeven, laat ik zo maar een aantal wetenswaardigheden en eigenaardigheden van priemgetallen de revue passeren. Ik wens de geachte lezer weer veel plezier.
Definitie
Een priemgetal is een getal met precies twee delers, nl. 1 en zichzelf. Dit betekent dat 1 geen priemgetal is. Het eerste priemgetal is 2, dit is tevens het enige even priemgetal, daar alle andere even getallen, buiten 1 en zichzelf, ook 2 als deler hebben! Verdere voorbeelden zijn 3, 5, 7, 11, 13, 17 … Zoals in de vorige aflevering is bewezen, zijn er oneindig veel priemgetallen.
Priemtweelingen
Een priemtweeling is een paar priemgetallen (twee dus) die als onderling verschil 2 hebben. Voorbeelden zijn: (3,5), (5,7), (11,13), (17,19) … Men denkt dat er ook oneindig veel priemtweelingen bestaan, maar dat is tot op heden niet bewezen.
Regelmaat
Vele wiskundigen, en ook anderen, hebben geprobeerd regelmaat te ontdekken in priemgetallen. Hiermee hoopte men een formule te kunnen ontdekken die priemgetallen zou voortbrengen. Euler heeft de volgende formule bedacht: n2 + n + 41. Voor n=1 tot 40 gaat dit goed. Maar bij n=40 gaat dit mis. Het is overigens opmerkelijk hoe goed deze formule is. De zoektocht naar regelmaat heeft echter nooit vruchten afgeworpen. Daaruit kunnen we concluderen dat er geen regelmaat is.
Reeksen zonder priemgetallen
Het vreemde doet zich voor dat er reeksen zijn waar helemaal geen priemgetallen in voorkomen. Kijk bv. maar eens naar de volgende reeks: 3628802, 3628803, 3628804, 3628805, 3628806, 3628807, 3628808, 3628809, 3628810. Deze getallen lijken misschien willekeurig maar zijn dat allerminst. Ik weet zeker dat de voornoemde getallen alle 9 zijn samengesteld ofwel geen priemgetal bevatten. Ze zijn namelijk als volgt opgebouwd: 10! + 2 t/m 10! + 10. n! staat voor het product van de getallen 1 t/m n, ook wel de faculteit van n genoemd. Door de opbouw van de getallen n! + 2 t/m n! + n weet ik zeker dat n! + 2 deelbaar is door 2, dat n! + 3 deelbaar is door 3, dat n! + n deelbaar is door n, ga zelf maar na. Ik kan dus willekeurig grote reeksen getallen maken waarvan ik zeker ben dat er geen priemgetallen tussen zitten, dit is op z’n minst curieus te noemen.
Genereren van priemgetallen
Daar er geen formule is om priemgetallen te genereren gaan we eens kijken naar andere methodes. Daar de computer aardig kan rekenen gaan we eens kijken naar wat algoritmes, recepten, die priemgetallen kunnen voortbrengen. Bij de volgende voorbeelden gaan we uit van de volgende veronderstellingen: Breng alle priemgetallen voort tot een aangegeven maximum.
Rechttoe rechtaan
Uit de definitie volgt dat wanneer een willekeurig getal geen delers heeft anders dan 1 en zichzelf het een priemgetal is. Het volgende algoritme test een willekeurig getal of het deelbaar is door de getallen 2 t/m het getal – 1, wanneer dat zo is, dan is het geen priemgetal, anders wel. Het algoritme in pseudotaal:
1 Max = Invoer
2 Voor Getal = 2 Tot Max
3 Voor Deler = 2 Tot Getal-1
4 Als Getal Modulo Deler = 0 GoTo 8
5 Volgende Deler
6 Print Getal ” is een priemgetal”
7 GoTo 10
8 Print Getal ” is geen priemgetal”
9 Volgende Getal
10 Print “Klaar”
In regel 1 vragen we om invoer. In regel 2 starten we een lus om te kijken welke getallen vanaf 2 t/m ons ingevoerde getal priem zijn. In regel 3 starten we een lus die gaat kijken naar de delers van het dan te testen getal. In regel 4 staat de daadwerkelijke test, wanneer de rest van het te testen getal gedeeld door de deler nul is dan is het getal dus deelbaar door deler en daarmee niet priem, we verlaten dan de lus. Wanneer de test niet opgaat gaan we in regel 5 de volgende deler testen. Wanneer we de tweede lus volledig hebben doorlopen is er dus geen deler gevonden, en daarmee het te testen getal priem. De rest spreekt hopelijk voor zich.
Dit algoritme werk wel, maar is niet erg efficiënt.
Een slimmer algoritme
Kijk eens naar de delers van het getal 12, dat zijn 1, 2, 3, 4, 6, 12. De zelfde delers, maar nu in een andere volgorde: 1, 12, 2, 6, 3, 4. Als ik weet dat 1 een deler is, dan weet ik ook dat 12 dat is, wanneer ik weet dat 2 een deler is, dan weet ik ook dat 6 dat is en wanneer ik weet dat 3 een deler is, dan weet ik ook dat 4 dat is. Met andere woorden, in het geval van 12 hoef ik maar te testen tot 3 om de conclusie te trekken dat 12 geen priemgetal is, eigenlijk maar tot 2, maar goed. De vraag is: waar ligt het omslagpunt, ofwel tot waar moet ik testen om er zeker van te zijn dat een getal priem is? Het antwoord luidt: tot de wortel van het getal. Dit kunnen we toepassen in ons algoritme, waarmee ons algoritme opeens een stuk sneller wordt:
1 Max = Invoer
2 Voor Getal = 2 Tot Max
3 Voor Deler = 2 Tot Wortel(Getal)
4 Als Getal Modulo Deler = 0 GoTo 8
5 Volgende Deler
6 Print Getal ” is een priemgetal”
7 GoTo 10
8 Print Getal ” is geen priemgetal”
9 Volgende Getal
10 Print “Klaar”
Een andere benadering
Een van de wetten van de rekenkunde zegt dat ieder getal op unieke wijze te ontbinden is in priemfactoren. Een gevolg daarvan is dat ik in mijn algoritme alleen maar hoef te kijken of het te testen getal deelbaar is door een van de priemfactoren kleiner of gelijk aan de wortel van het te testen getal. Dat vermindert uiteraard weer het aantal testen. Echter komt er wel wat administratie voor in de plaats, ik moet namelijk nu alle priemgetallen gaan onthouden! De vraag is dan ook wanneer dit algoritme efficiënter is dan het vorige. Dat is pas bij relatief grote getallen. Hier dan het algoritme:
1 Max = Invoer
2 Index = 1
3 Priem[Index] = 2
4 Voor Getal = 3 Tot Max
5 Teller = 1
6 Zolang Teller <= Index And Priem[Index] <= Wortel(Getal) And Getal Modulo Priem[Index] <> 0
7 Teller = Teller + 1
8 Einde Zolang
9 Als Teller > Index
10 Print Getal ” is een priemgetal”
11 Index = Index + 1
12 Priem[Index] = Getal
13 Anders
14 Print Getal ” is geen priemgetal”
15 Einde Als
16 Volgende Getal
17 Print “Klaar”
De Zeef van Erathostenis
Een hele andere benadering is het algoritme dat bedacht werd door een wiskundige uit de 10 eeuw na Christus, Erathostenis genaamd. Hij bedacht de zeef. Dit gaat als volgt: Stop alle getallen vanaf 2 t/m het maximum geordend in een bak. Het eerste getal is een priemgetal, zeef vervolgens alle veelvouden van dat getal uit de bak en begin vervolgens weer van voren af aan. Herhaal dit totdat er slechts nog priemgetallen in de bak zitten. Het blijkt dat dit algoritme zeer efficiënt is.
RSA-encryptie
Zoals in de inleiding reeds opgemerkt, spelen priemgetallen een belangrijke rol bij encryptie. Een populair encryptie-algoritme is op dit moment PGP, dat staat voor Pretty Good Privacy. Dit systeem is afgeleid van een systeem dat werd bedacht door Rivest, Shamir en Adlemann en de geschiedenis is ingegaan als het RSA-systeem.