Getallen; je komt er dagelijks mee in aanraking. Is het niet bij de wiskundeles, dan is het wel bij het afrekenen bij de kassa van de supermarkt. Niet alleen het bedrag dat je moet betalen wordt weergegeven met getallen, ook de barcodescanner maakt gebruik van bijzondere eigenschappen van een bepaald soort getallen. Ja, je leest het goed, er wordt inderdaad gesproken over een bepaald soort getallen. Er bestaan namelijk verschillende verzamelingen van getallen, elk met andere eigenschappen. In deze tekst bekijken we een groep getallen die wetenschappers al vele jaren fascineert; de priemgetallen. En laten priemgetallen nou net de getallen zijn waar de barcodescanner gebruik van maakt.
De klassieke indeling
In de wiskunde worden getallen ingedeeld in verzamelingen. Een verzameling wordt in de wiskunde gedefinieerd als een collectie van verschillende objecten die bij elkaar horen. Elke verzameling heeft een naam. De bekendste verzameling getallen heet N. N bestaat uit alle positieve gehele getallen: 0,1,2 etc, ook wel de natuurlijke getallen genoemd. In de eerste klas heb je de negatieve getallen leren kennen. Alle gehele positieve en negatieve getallen samen vormen de verzameling Z.
Wat zijn priemgetallen?
Een priemgetal is een getal groter dan 1 en alleen deelbaar door 1 en zichzelf. Een getal dat groter dan 1 is en bovendien deelbaar is door een ander getal dan zichzelf heet een samengesteld getal. Je vraagt je wellicht af wat er zo bijzonder is aan priemgetallen. Deze vraag wordt beantwoord door de hoofdstelling van de rekenkunde. Deze stelling zegt dat alle getallen in ons dagelijks leven zijn opgebouwd uit priemgetallen oftewel dat ieder getal te schrijven is als een keersom met alleen maar priemgetallen.
Zo is 23244 te schrijven als 2x2x3x13x149 en dat zijn weer allemaal priemgetallen. Deze keersom heet de priemgetalfactorisatie van een getal.
Eratosthenes.
Hoe vind je priemgetallen?
Ondanks dat wiskundigen zich al eeuwen bezighouden met priemgetallen, is er nog steeds geen formule gevonden die van een getal direct kan vaststellen of het een priemgetal is of niet. Er zijn wel algoritmes ontwikkeld die dat kunnen. Een algoritme is een lijst met instructies die van een bepaalde begintoestand leiden tot een beoogd einddoel. Bij het algoritme dat bekijkt of een getal een priemgetal is, vormt het getal de begintoestand en is het beoogde einddoel om te weten of een getal wel of geen priemgetal is. Zo’n algoritme heet ook wel een priemgetaltest.De Griekse wetenschapper Eratosthenes bedacht al in 263 voor Christus, ver voor de tijd van computers, een simpel algoritme om priemgetallen te vinden. Het algoritme dat hij samenstelde wordt ook wel de zeef van Eratosthenes genoemd:
- Schrijf alle getallen vanaf 2 tot een zelf te kiezen getal op.
- Kies het kleinste getal uit dat je hebt opgeschreven.
- Streep alle getallen door die deelbaar zijn door het gekozen getal, maar niet het getal zelf.
- Kies het volgende getal uit de lijst en ga weer terug naar stap 3.
Getallenspiraal.
Magie van priemgetallen
Dat priemgetallen mysterieus zijn blijkt wel uit de volgende uitspraak van Paul Erdos, een zeer getalenteerd en beroemd wiskundige: “God dobbelt misschien niet met het heelal, maar er is iets vreemds aan de hand met de priemgetallen”.Dat priemgetallen mysterieus zijn, heeft ook de wiskundige Ulam aan den lijve ondervonden. Toen hij zich op een wetenschappelijk congres verveelde heeft hij op een blaadje alle natuurlijke getallen in een spiraal neergezet (zie figuur 1). Alle priemgetallen heeft hij toen omcirkeld. Het viel hem al vrij snel op dat de priemgetallen zich meestal op de diagonalen bevinden. Als de spiraal wordt uitgebreid en alle priemgetallen niet worden omcirkeld, maar worden opgelicht, geeft dat als resultaat figuur 2. Deze afbeelding staat ook wel bekend als de spiraal van Ulam. Bijzonder aan deze afbeelding is dat we enige regelmaat in de afbeelding kunnen ontdekken (let op de diagonalen!), terwijl er altijd van uit werd gegaan dat in priemgetallen geen regelmatig patroon te ontdekken was. Er is dus nog veel te ontdekken over priemgetallen.
Spriraal van Ulam.
Toepassingen van priemgetallen
Een van de modernste en meest gebruikte toepassingen van priemgetallen is het beveiligen van informatie, bijvoorbeeld op een bankpas maar ook in een geheime boodschap van de CIA. Hoe werkt die beveiliging via priemgetallen?
Om een bericht te versleutelen zijn er twee getallen nodig, N en e. N is de vermenigvuldiging van twee heel grote priemgetallen en e is een door de versleutelaar gekozen getal. Om het bericht te ontsleutelen zijn er weer twee getallen nodig, ditmaal N en d. Om d te berekenen heb je de twee priemgetallen nodig die bij vermenigvuldiging N opleveren. Om deze getallen te vinden zal je alle mogelijke combinaties van priemgetallen moeten uitproberen. Omdat N namelijk is opgebouwd uit twee priemgetallen bestaat er geen computerprogramma dat dat efficiënter kan doen. Dit uitproberen door de computer duurt langer dan een mensenleven! De boodschap kan dus alleen ontgrendeld worden als bij de ontsleutelaar de priemgetallen waaruit N is opgebouwd bekend zijn.
Voorbeeld
Nu een voorbeeld van bovenstaande versleuteling. Stel dat de versleutelaar en de ontsleutelaar het volgende afspreken: het getal d is de optelsom van de twee priemgetallen waaruit N is opgebouwd.
Stel dat de versleutelaar 47497x47501= 2256154997 als getal N heeft gekozen en 10 als getal e. Als de ontsleutelaar dan 47497+47501=94998 als getal d kiest, kan hij de boodschap ontsleutelen. Het getal e heeft een controlerende functie die voor de ontsleutelaar niet van belang is.