Een nieuw priemrecord: zonde van de tijd?


Een kortere versie van deze blog verscheen eerder in Eos Magazine Editie 3 (2016).

 

Op hun website mersenne.org kondigde het vrijwilligersproject GIMPS op 7 januari 2016 de vondst aan van een nieuw recordpriemgetal, een getal met meer dan 22 miljoen cijfers:
grootste
Het is het grootste priemgetal dat op dit moment gekend is. Ter herinnering, priemgetallen (2, 3, 5, 7, 11, 13, 17,…) kunnen niet geschreven worden als het product van andere getallen, ze zijn per definitie enkel deelbaar door 1 en door zichzelf. De Griekse wiskundige Euclides heeft in de 3de eeuw v. C. formeel bewezen dat er oneindig veel priemgetallen zijn, dus op zich is het geen verrassing dat we steeds maar grotere priemgetallen ontdekken.

EuclidsElements(Een deel van de Oxyrhynchus papyrus uit ongeveer 100 v.C. met een van de oudste bewaard gebleven fragmenten uit de Elementen van Euclides. In deze meer dan 2000 jaar oude boeken zijn de priemgetallen al prominent aanwezig.)

Toch moet de vondst van een nieuw recordpriemgetal als een huzarenstuk beschouwd worden, want er bestaan nog altijd geen effectieve methodes om een priemgetal met bijvoorbeeld 400 cijfers te genereren, of om van een gegeven getal na te gaan of het priem is. Een moderne computer heeft meer tijd nodig dan de leeftijd van het heelal om een getal met 1000 cijfers te testen.

Het nieuwe record staat dus op naam van GIMPS, de afkorting voor Great Internet Mersenne Prime Search . Dit project verbindt momenteel wereldwijd, op universiteiten maar ook bij vrijwilligers thuis, meer dan 1.200.000 computerprocessoren die tijdens piekmomenten ongeveer $450\times 10^{12}$  berekeningen per seconde doen. GIMPS zoekt grote priemgetallen van de vorm $2^p-1$ met $p$ zelf een priemgetal, Mersenne-priemgetallen genoemd, naar de 17de-eeuwse wiskundige Marin Mersenne.

mersenne (Afbeelding van Marin Mersenne, de Franse priester en wiskundige die zijn naam gaf aan de Mersenne-priemgetallen.)

Voor getallen van de vorm $2^p-1$ bestaan er iets snellere testen om na te gaan of het een priemgetal is. Vandaar dat GIMPS enkel deze kandidaten nagaat. Niet toevallig zijn alle recente records inderdaad Mersenne-priemgetallen (zie onderstaande tabel). Tegelijkertijd moeten we wel waarschuwen voor het feit dat wiskundigen nog altijd niet weten of er oneindig veel Mersenne-priemgetallen, dus iedere recordprestatie van GIMPS zou wel eens de laatste kunnen zijn.tabel
De ontdekking van een nieuw record mag dan wel steevast op applaus rekenen en de pers halen, de meeste mensen vragen zich ongetwijfeld af waarom zoveel energie gespendeerd worden aan het zoeken naar gigantische priemgetallen. Vanwaar deze heisa? Is dit geen zonde van al dat geld en al die tijd? Deze kritiek, die misschien niet helemaal onterecht is, wordt kurkdroog geformuleerd in onderstaande lezersbrief uit The Washington Post van 22 juni 1993, die wel confronterend is voor wiskundigen. Het is een reactie op een oplossing voor een probleem in Ramsey-theorie, een deelgebied van wiskunde waarin onderzocht wordt hoeveel elementen er minstens vereist zijn opdat de groep bepaalde eigenschappen bezit.

RamseyBrief Slik, dit komt binnen. Zonder bovenstaande kritiek volledig te ontkrachten, proberen we toch enkele motivaties op te sommen die het werk van priemjagers een beetje rechtvaardigen. Omdat we al heel ons leven wiskunde doceren en verspreiden onder de medemens, zijn we het immers gewoon om advocaat van de duivel te spelen.

Voor de wiskunde. Ook al zijn priemgetallen de bouwstenen van de getaltheorie (elk getal kan op een unieke manier geschreven worden als een product van priemgetallen), hun spreiding is zo grillig dat ze de wiskundigen al eeuwen in de ban houden. Zoeken naar grote priemgetallen behoort dan ook tot de wiskundige folklore, met als gunstig bijverschijnsel dat de studie ervan leidt tot nieuwe inzichten en tot het ontstaan en de bloei van deelgebieden binnen de getaltheorie. In verband hiermee willen we zeker een van de grootste wiskunderaadsels van het moment vermelden, het nog steeds onopgeloste miljoen dollar Riemann-vermoeden.

Voor de veiligheid. Grote priemgetallen vormen de basis van de RSA-versleuteling, het meest gebruikte beveiligingssysteem voor banktransacties, internetverkeer en andere communicatie die tegen luistervinken moet beveiligd worden. De huidige RSA implementaties gebruiken zeer grote priemgetallen, tussen de 300 en de 600 cijfers. Er zijn ongeveer 10297 priemgetallen met 300 cijfers, ruim voldoende en lang genoeg om de veiligheid van generaties geheimen te waarborgen, dus de recordpriemgetallen van de laatste decennia kunnen niet verkocht worden aan het grote publiek als zijnde van enig praktisch nut hierbij.

Voor de mystiek. De oude Grieken waren gefascineerd door zogenaamde volmaakte getallen, getallen die in evenwicht zijn met hun delers. Een volmaakt getal is exact gelijk aan de som van zijn delers, 1 meegerekend maar het getal zelf natuurlijk niet. Bijvoorbeeld: 6=1+2+3 is perfect in balans. Als de som van de delers (behalve het getal zelf) strikt kleiner is dan het getal, dan beschouwden de Grieken dit getal als gebrekkig. Als deze som groter is dan het getal in kwestie, dan noemden de Grieken ze overvloedig of overdadig. Priemgetallen zijn uiterst gebrekkig wegens de afwezigheid van delers, maar ook bijvoorbeeld 8 schiet te kort: 1+2+4 < 8. Het getal 12 heeft dan weer te veel delers en is overvloedig: 1+2+3+4+6 > 12. De Grieken, maar ook de Egyptenaren, en later de Christenen schreven mystieke en religieuze eigenschappen toe aan de volmaakte getallen. Nochtans waren er in de oudheid maar vier gekend: : 6, 28, 496 en 8128. Merk op dat al deze volmaakte getallen even zijn. Tot nu toe heeft men nog geen enkel oneven volmaakt getal gevonden en er zijn sterke aanwijzingen dat oneven volmaakte getallen niet bestaan. Maar helemaal zeker zijn we nog niet. Dit is waarschijnlijk het oudste onopgeloste probleem van de wiskunde!

Maar wat heeft dit nu allemaal te maken met de recordpriemgetallen die door GIMPS ontdekt werden? Wel, Euclides had namelijk een procedé ontdekt om volmaakte getallen te construeren. Neem een Mersenne-priemgetal $2^p-1$ (Euclides gebruikte uiteraard niet deze benaming) dan levert $2^{p-1}\times (2^{p} - 1)$ gegarandeerd een volmaakt getal op. Later, in de 18de eeuw, bewees Euler dat alle even volmaakte getallen op deze manier kunnen gemaakt worden:

$p = 2:$ $2^{1}\times (2^{2} -1) = 6$

$p = 3:$ $2^{2}\times (2^{3} -1) = 28$

$p = 5:$ $2^{4}\times (2^{5} -1) = 496$

$p = 7:$ $2^{6}\times (2^{7} -1) = 8128$

Sinds januari van dit jaar kennen we 49 Mersenne-priemgetallen, en dus ook 49 volmaakte getallen. Geen mens die weet hoeveel er nog wachten om ontdekt te worden.

Voor het testen van hardware. Al bij de constructie van de eerste computers werden priemtesten gebruikt om de hardwarefouten op te sporen. Zo werden bijvoorbeeld GIMPS-programma’s door Intel gebruikt om de Pentium II en Pentium Pro chips te testen voordat ze de deur uitgaan. Een ander gigantisch rekenproject (met priemgetallen) heeft in 1994 de beruchte Pentiumbug blootgelegd. En deze maand nog heeft software van GIMPS een fout ontdekt in de nieuwe Intel Skylake processor. Is het zoeken naar grote (Mersenne-)priemgetallen dan toch nuttig?

Maar misschien doen we het gewoon…

Voor het geld. Grote priemgetallen zoeken mag zeker als een prestigewedstrijd bekeken worden, met bijbehorende winstpremies, zoals in andere sporten. De Electronic Frontier Foundation (EFF) is een Amerikaanse consumentenbond toegespitst op de rechten en de privacy van internetgebruikers. Dankzij de donaties van een mysterieuze sympathisant heeft de EFF de mogelijkheid om prijzen uit te loven aan priemrecordbrekers, met als doelstelling de wereldwijde computersamenwerking te stimuleren. Ieder nieuw grootste priemgetal verdient $\$$3000. De eerste die een priemgetal vindt met meer dan 100.000.000 cijfers wint $\$$150.000, meer dan 1 miljard cijfers levert $\$$250.000 op.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 


2 reactie op “Een nieuw priemrecord: zonde van de tijd?”

  1. Filip Beantwoorden | Permalink

    >> "elk getal kan op een unieke manier geschreven worden als een product van priemgetallen"
    Hoe schrijf je dan een priemgetal (bvb. 13) als een product van priemgetallen? NB: 1 is géén priemgetal dus 13x1=13 kan niet.

  2. Rudi Penne en Paul Levrie Beantwoorden | Permalink

    Jouw opmerking is terecht. Maar wiskundigen praten zich hier uit door het begrip `product' flexibel te bekijken. Een doordeweeks product telt 2 factoren. We kunnen uiteraard langere producten beschouwen, maar ook kortere. Een product met 1 factor bijvoorbeeld. Bijvoorbeeld, 13 is een product op zich met 1 factor. Straffer, we definiëren zelfs een product met 0 factoren; de uitkomst hiervan is gelijk aan 1! Onze verborgen agenda bij het maken van dergelijke afspraken is om achteraf een wiskundige eigenschap bondig en elegant te formuleren (zonder vervelende uitzonderingen). Bedankt voor je commentaar!

Een reactie geven