Ik legde in een explainer uit hoe Heel kort vertelde ik dat priemgetallen onontbeerlijk zijn. Voor de echte die hard leg ik ook nog even uit wat priemgetallen zijn en wat ze zo bijzonder maakt.

Het grootste bekende priemgetal, 2^57.885.161 – 1, bestaat uit bijna 17,5 miljoen cijfers. ‘Je kunt het zien als het vinden van een diamant,’ reageerde wiskundige Curtis Cooper enthousiast bij de ontdekking van het getal. Maar wat zijn priemgetallen eigenlijk en hoe zorgen deze grote getallen ervoor dat jij en ik veilig data kunnen uitwisselen?

Priemgetallen zijn getallen die alleen deelbaar zijn door zichzelf en door één. Bijvoorbeeld:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29 etcetera.

Alle priemgetallen, op twee na, zijn oneven. Dat is logisch want even getallen zijn doorgaans deelbaar door andere getallen. Wiskundigen hebben afgesproken dat één geen priemgetal is.

Al eeuwen lang zijn wiskundigen op zoek naar de geheimen achter priemgetallen. Driehonderd jaar voor Christus bewees de Griekse wiskundige Euclides in zijn werk Elementen dat er oneindig veel priemgetallen zijn. Om de paar jaar wordt er een nieuw priemgetal

Vroeger was de zoektocht naar priemgetallen voorbehouden aan wiskundigen, inmiddels zijn er projecten waarbij duizenden mensen over de hele wereld gezamenlijk zoeken naar een nieuw priemgetal. Zo is het grootst bekende priemgetal 2^57.885.161 – 1 ontdekt door Curtis Cooper, die meedeed aan het project GIMPS (Great Internet Mersenne Prime Search). Het project verbindt duizenden in een zoektocht naar het zogenoemde Mersennepriemgetallen. Dit zijn priemgetallen die 1 kleiner zijn dan een macht van twee.

Wat hebben we hieraan?

Allemaal leuk en aardig, die liefde van wiskundigen voor gigantische priemgetallen, maar wat hebben we er eigenlijk aan? Priemgetallen zijn de bewakers van ons internetverkeer. De meest gebruikte vorm van public key encryption is RSA, genoemd naar het gelijknamige bedrijf en de oprichters Ron Rivest, Adi Shamir en Len Adleman. Als je belastingaangifte doet via DigID, een e-mail stuurt via Gmail of een Facebookbericht plaatst, gebruik je deze encryptie. RSA maakt vaak deel uit van De veiligheid van RSA berust op de ontbinding van gigantische getallen in priemfactoren. Dat klinkt ingewikkeld, maar het principe is simpel.

Door twee gigantische priemgetallen van meer dan driehonderd cijfers te vermenigvuldigen krijg je een getal dat níet priem is. De twee priemgetallen vormen samen je privésleutel. De uitkomst, ook wel een semi-priemgetal genoemd, is je publieke sleutel die je met iedereen deelt.

Twee priemgetallen vermenigvuldigen is simpel. Maar berekenen welke priemgetallen zijn gebruikt om tot het semi-priemgetal te komen, is bijna Omdat sommige getallen te groot zijn om volledig uit te schrijven, geven we ze weer in factoren. Zo kan je 36 ook schrijven als 2^2 X 3^2.

Op 31 oktober 1903 ontbond de Amerikaanse wiskundige Frank Nelson Cole tijdens een van zijn colleges het gigantische getal 147.573.952.589.676.412.927= 2^67-1 in twee priemgetallen. Zonder computer had hij drie jaar lang, iedere zondag gezocht naar de ontbinding van het getal. Als Cole anno 2014 in staat zou zijn om getallen van meer 300 cijfers te ontbinden, zouden we een groot beveiligingsprobleem hebben. Gelukkig is dit onmogelijk en doen zelfs computers met extreem veel rekenkracht er jaren over om dergelijke getallen te ontbinden.

De grootst ontbonden encryptiesleutel die bekend is, is een sleutel van 1061 bits (320 cijfers). Dit kostte negentien maanden. Wetenschappers verbonden een half miljoen computers met elkaar.

Is ontbinden dan toch mogelijk?

Vorige maand werd bekend dat de NSA werkt aan een kwantumcomputer, een supercomputer die heel snelle parallelle berekeningen kan uitvoeren en daarmee alle RSA-encryptie zou kunnen kraken. Toch kunnen we voorlopig gerust zijn. De NSA is nog niet erg ver in de ontwikkeling van de kwantumcomputer. Ook een onderzoeksgroep van de TU Delft ontwikkelt een kwantumcomputer. Binnen zes jaar hopen ze een werkend prototype te kunnen presenteren.

Gelukkig zitten wiskundigen en informatici niet stil en wordt er al encryptie ontwikkeld voor een computer die alleen nog op papier bestaat. Zodoende zijn inlichtingendiensten, hackers en encryptieontwikkelaars verwikkeld in een oneindige wapenwedloop.

YouTube
Why I fell in love with monster prime numbers. Adam Spencer legt priemgetallen helder uit in deze TED Talk.

Meer weten over priemgetallen? Lees dan de Pracht van priemgetallen van Paul Levrie en Rudi Penne. Bekijk hier het boek