Priemgetal
Volgens wikipedia is een priemgetal een natuurlijk getal groter dan 1 dat slechts twee natuurlijke getallen als deler heeft, namelijk 1 en zichzelf. Het kleinste priemgetal is dus 2, want het heeft alleen 1 en 2 als delers.
Om dit te kunnen begrijpen moet je eerst weten wat een natuurljk getal is: Natuurlijke getallen zijn alle positieve hele getallen, te weten 
Deze getallen worden aangegeven met het symbool 
. Er is geen overeenstemming of het getal 0 bij de natuurlijke getallen hoort. In de traditionele definitie beginnen de natuurlijke getallen bij 1 (van daaraf begint men immers te tellen), maar vanaf de negentiende eeuw ziet men de definitie opduiken die 0 wel tot de natuurlijke getallen rekent. In de wiskunde wordt tegenwoordig vrij algemeen het getal 0 tot de natuurlijke getallen gerekend.
Priemgetallen vormen een belangrijk onderwerp in het deelgebied van de wiskunde, dat getaltheorie genoemd wordt.
Priemgetallen werden reeds door de oude Grieken bestudeerd. Er zijn oneindig veel priemgetallen. Het bewijs hiervoor wordt gegeven door de stelling van Euclides.
Sinds de uitvinding van de elektronische computers is het grootst bekende priemgetal bijna altijd een mersennepriemgetal geweest.
mersennepriemgetal: een positief geheel getal dat precies één kleiner is dan een macht van twee, in een formule ziet dit er als volgt uit:
Het grootste bekende priemgetal (gevonden in december 2018) is het getal 282 589 933-1 en bestaat uit 24 862 048 cijfers. De volgende tabel geeft de grootste bekende priemgetallen van de genoemde soorten:
| Priemgetal |
Aantal decimale cijfers |
Soort |
Datum |
Gevonden door |
| 282 589 933 − 1 |
24 862 048 |
mersennepriemgetal |
december 2018 |
Patrick Laroche (Gimps) |
| 277 232 917 − 1 |
23 249 425 |
mersennepriemgetal |
26 december 2017 |
Jon Pace |
| 19 249 × 213 018 586 + 1 |
3 918 990 |
niet een mersennepriemgetal (Proth-getal) |
26 maart 2007 |
Seventeen or Bust |
| 150 209! + 1 |
712 355 |
factoriaal priemgetal |
oktober 2012 |
PrimeGrid |
| 1 098 133# - 1 |
476 311 |
primoriaal priemgetal |
maart 2012 |
PrimeGrid |
| 3 756 801 695 685 × 2666 669 ± 1 |
200 700 |
priemtweeling |
december 2011 |
PrimeGrid |
De Electronic Frontier Foundation heeft in 2009 een prijs van 100.000 dollar toegekend aan GIMPS voor het als eerste ontdekken van een priemgetal dat ten minste uit 10 miljoen cijfers bestaat. Door dezelfde organisatie zijn ook prijzen van respectievelijk 150.000 en 250.000 dollar uitgeloofd voor priemgetallen van respectievelijk minimaal 100 miljoen en 1 miljard cijfers.
Nu we weten wat een priemgetal is, is het natuurlijk ook interessant om te weten wat je ermee kunt of waar het gebruikt wordt.
In de natuur is er in de evolutionaire strategie een voorbeeld van priemgetallen.
De cicaden (insecten van het geslacht Magicicada) brengen het grootste deel van hun leven als larven ondergronds door. Ze verpoppen zich en komen vervolgens pas na 13 of 17 jaar uit hun holen, waarna zij rondvliegen, paren en dan na hoogstens een paar weken sterven. De logica van de 13- en 17-jarige cyclus is dat men veronderstelt dat deze priemgetalintervallen het voor roofdieren erg moeilijk maken zich in een richting te ontwikkelen dat zij zich in enige mate als roofdieren op Magicicadas kunnen specialiseren. Als Magicicadas met niet-priemgetal-tussenpozen zou verschijnen, zeg elke 12 jaar, dan zouden roofdieren, die elke 2, 3, 4, 6 of 12 jaar zouden verschijnen er zeker van kunnen zijn om Magicicades exemplaren tegen te komen om deze vervolgens te verorberen. Door natuurlijke selectie zouden zij hier langzamerhand beter in kunnen worden. Over een 200-jarige periode zou de gemiddelde roofdierbevolking tijdens hypothetische uitbraken van 14- en 15-jaar cicaden tot 2% hoger zijn dan tijdens uitbraken van 13- en 17-jaar cicaden. Hoewel klein lijkt dit voordeel genoeg te zijn om de natuurlijke selectie in de richting van een priem-genummerde levenscyclus van deze insecten te sturen.
Priemgetallen worden ook toegepast in verschillende delen van de informatietechnologie, onder andere bij het beveiligen van digitale informatie, door middel van cryptografie, maar waarom zijn priemgetallen nou zo belangrijk.
De zoektocht naar priemgetallen is geen prestigezaak voor verveelde wiskundigen. De getallen hebben een bijzonder praktisch nut en de mathematische logica erachter is een fundamentele bouwsteen in tal van applicaties in de moderne digitale wereld. Dat komt omdat ieder geheel getal zonder uitzondering uitgedrukt kan worden als een product van uitsluitend andere priemgetallen. Priemgetallen zijn getallen die je niet verder uit elkaar kan trekken (je kunt ze alleen maar door het getal 1 en zichzelf delen). Ontbind je een groot getal in steeds kleinere getallen, dan is het onvermijdelijk dat je na verloop van tijd op priemen strandt. Hieronder een voorbeeld:
 |
Het getal 144 kun je dus schrijven als 2 x 2 x 3 x 3 x 2 x 2. Dit zijn weer allemaal priemgetallen. |
Het is niet zo moeilijk om een relatief laag geheel getal te ontbinden in priemfactoren. Je hebt er je hersenen en een beetje tijd voor nodig en je hebt dit in de 1e klas al moeten doen. Hoe groter de getallen, hoe moeilijker echter de ontbinding wordt. Er is immers, voor zover wiskundigen weten, geen efficiënte formule waarmee je eender welk getal kan ontbinden.
Er bestaan natuurlijk wel technieken, maar uit hoe meer cijfers een getal bestaat, hoe moeilijker en minder efficiënt die worden. Een brutekrachtaanval op het getal 8 voor de ontbinding in 2 x 2 x 2 is niet zo moeilijk, maar wanneer een krachtige supercomputer de opdracht krijgt om een getal met 500 cijfers te ontbinden in priemfactoren, dan heeft die meer tijd nodig dan de totale leeftijd van de aarde.
Er bestaat met andere woorden geen wiskundige maar wel een praktische limiet voor de grootte van getallen die we kunnen ontbinden in priemfactoren en op dat feit is moderne computerbeveiliging gebouwd.
Eerst en vooral staan we even stil bij de manier waarop een beveiligde connectie tussen computers tot stand komt. Beveiligde verbindingen over het internet worden per definitie opgezet in een onbeveiligde omgeving. Dat gebeurt door encryptiesleutels uit te wisselen. Die sleutels zijn publiek te onderscheppen, maar ze dienen enkel om data te versleutelen. De sleutel voor de decryptie verschilt van de encryptiekey, en die wordt niet zomaar verzonden.
De absurde rekenkracht die nodig is om getallen in factoren te ontbinden maakt die werkwijze mogelijk. Beeld je ter illustratie twee gigantische priemgetallen in, bestaande uit honderden cijfers. Wanneer je die priemgetallen met elkaar vermenigvuldigt, krijg je een enorm getal dat deelbaar is door één, zichzelf en de twee priemgetallen waaruit het is opgebouwd. De priemen vermenigvuldigen om het grote getal te krijgen is niet moeilijk, maar andersom is het praktisch onmogelijk om, zelfs met ’s werelds krachtigste supercomputer, het enorme getal terug in z’n factoren te ontbinden.
Het grote getal kan in dit geval dienst doen als publieke sleutel. Die sleutel wordt over het internet verzonden om de beveiligde verbinding op te zetten. De computer die de key ontvangt, versleutelt er data mee, maar kan die zelf niet ontcijferen. Dat kan geen enkele computer, behalve degene die de publieke sleutel in eerste instantie genereerde. Dat systeem is immers op de hoogte van de twee priemgetallen waaruit de publieke sleutel bestaat.
Onderschept een hacker de sleutel dan kan hij data versleutelen, maar zonder de twee oorspronkelijke priemgetallen is decryptie onmogelijk. Twee computers die sleutels uitwisselen met elkaar kunnen zo beveiligd over het internet communiceren. Ze krijgen ieder een sleutel, coderen er data mee, zenden die naar hun respectievelijke communicatiepartner en enkel daar kan de data ontcijferd worden. Hoe de encryptie zelf precies in z’n werk gaat, is een ander verhaal, voor nu is het belangrijk te weten dat priemgetallen het fundament van het proces zijn.
