Priemgetallen van meer dan tien miljoen cijfers

Voor het eerst in de geschiedenis kennen we priemgetallen, getallen die slechts deelbaar zijn door 1 en door zichzelf, van meer dan tien miljoen cijfers. Twee reuzenpriemgetallen werden onlangs gevonden door de Amerikaan Edson Smith en de Duitser Hans Michael Elvenich, of beter gezegd: de computers van deze twee heren. De twee getallen, 243.112.609 – 1 en 237.156.667 – 1, zijn volledig uitgeschreven 12.978.189 respectievelijk 11.185.272 cijfers lang.

door

De rij priemgetallen begint zo: 2, 3, 5, 7, 11, 13, 17, 19. Het zijn de getallen die alleen deelbaar zijn door 1 en door zichzelf. Al zo’n 300 jaar voor Christus bewees de Griekse wiskundige Euclides dat er oneindig veel van zijn. Er bestaat dus geen allergrootste priemgetal, er zijn altijd nog grotere te vinden. Toch is maar van een eindig aantal getallen bekend of ze priem zijn. Dat komt doordat het testen op deelbaarheid bij grote getallen een tijdrovende klus is, ook voor snelle computers.

Op 23 augustus werd een nieuw reuzenpriemgetal gevonden: 243.112.609 – 1, een getal van maar liefst 12.978.189 cijfers. Ter vergelijking: het totale aantal cijfers van alle telefoonnummers in De Telefoongids van Amsterdam is ongeveer twee miljoen. Nooit eerder werd een priemgetal van meer dan tien miljoen cijfers gevonden. Het getal werd gevonden door (de computer van) Edson Smith, in het kader van GIMPS (Great Internet Mersenne Prime Search), een project waarbij duizenden vrijwilligers de ongebruikte rekencapaciteit van hun computer beschikbaar stellen voor via internet gedistribueerde berekeningen.

Op één pagina van De Telefoongids staan ruim 400 telefoonnummers van elk zeven cijfers. Als je alle telefoonnummers uit De Telefoongids van Amsterdam achter elkaar schrijft, krijg je een getal van ongeveer twee miljoen cijfers. Het nieuwe priemrecord is zes keer zo groot!

Twee jaar lang werden er bij GIMPS geen nieuwe resultaten geboekt. Maar zonder dat de priemspoorzoekers het zelf wisten, bleek er uiteindelijk sprake te zijn van een nek-aan-nek-race: twee weken nadat het oude priemrecord, daterend uit 2006, was gebroken, bleek dat (de computer van) GIMPS-deelnemer Hans-Michael Elvenich eveneens een priemgetal had gevonden: 237.156.667 – 1. Dit getal is met 11.185.272 cijfers iets kleiner dan dat van Edson Smith. Dat de twee nieuwe priemgetallen zo snel na elkaar zijn gevonden, is opmerkelijk. Want ondanks dat er oneindig veel priemgetallen bestaan, zijn ze steeds dunner gezaaid naarmate we hoger in de wereld van getallen komen.

Loterij

GIMPS heeft honderd duizend dollar uitgeloofd voor de eerste vinder van een priemgetal van meer dan tien miljoen cijfers. Dit prijzengeld gaat dus naar Edson Smith, een Amerikaan van de University of California, Los Angeles. Een knappe prestatie van de gelukkige winnaar kun je het echter niet noemen: als deelnemer van GIMPS krijg je een getal toebedeeld, waarna je computer het werk doet. De kans dat je computer na twee maanden rekenen goed nieuws heeft, is ongeveer één op 250.000. In feite doe je dus mee aan niets anders dan een loterij.

Het is zuur voor Hans-Michael Elvenich, een Duitser die werkzaam is bij een bedrijf dat chemische producten vervaardigt, dat hij net te laat is om zichzelf de eerste vinder te noemen van een priemgetal van meer dan tien miljoen cijfers. Elvenich reageert echter sportief: ‘After four years of searching for a prime on GIMPS, finally a great success!’

Priemgetallen spelen een belangrijke rol bij moderne coderingsmethodes. GIMPS-deelnemers dragen hier hun steentjes echter niet aan bij: daarvoor zijn de door hen gevonden priemgetallen veel te groot. De grote priemen die in de cryptografie worden gebruikt, hebben ‘slechts’ een paar honderd cijfers. Maar wie weet helpen de priemgiganten die door GIMPS worden gevonden in de toekomst de wetenschap nog vooruit. Het zou niet de eerste keer zijn dat iets achteraf, soms vele jaren later, ergens nuttig voor blijkt te zijn.

De Franse monnik Marin Mersenne (1588-1648) die zijn naam gaf aan deze priemgetallen.

Mersenne-priemgetallen

De nieuwe priemgetallen zijn van de vorm 2n – 1. Zulke getallen heten Mersenne-getallen, naar de Franse monnik en amateurwiskundige Marin Mersenne (1588-1648). Van deze soort getallen kan relatief makkelijk worden vastgesteld of ze priem zijn. De grote priemgetallen die de laatste jaren werden gevonden, zijn dan ook allemaal van deze vorm. De tijd die een computer nodig heeft om een groot Mersenne-getal op delers te controleren, kan oplopen tot twee maanden. Maar bij andersoortige getallen van dezelfde omvang kan zo’n berekening geen maanden, maar jaren duren!

GIMPS bestaat sinds januari 1996 en heeft sindsdien twaalf nieuwe Mersenne-priemgetallen opgeleverd. De initiators van GIMPS verifiëren de geclaimde successen van de deelnemers. Deze week bevestigden zij dat de twee recente vondsten inderdaad priemgetallen zijn.