Je leest:

Jubileum voor Mersenne-priemgetallen: de vijftigste is gevonden

Jubileum voor Mersenne-priemgetallen: de vijftigste is gevonden

Getal van 23.249.425 cijfers is nu het grootst bekende getal zonder delers

Auteur: | 11 januari 2018
Arnout Jaspers voor NEMO Kennislink

Voor zover bekend heeft het geen nut, maar duizenden liefhebbers zoeken naar extreem grote priemgetallen (getallen zonder delers). Op 3 januari 2018 kwam de bevestiging dat het vijftigste Mersenne-priemgetal gevonden is, door een computer van Jonathan Pace in de Verenigde Staten. Hij draait mee in de Great Internet Mersenne Prime Search (GIMPS).

De eerste 1800 cijfers van het vijftigste Mersenne-priemgetal (zie ook de header-afbeelding). De zwarte blokjes geven de cijfers aan die – bij toeval – de eerste 22 gewone priemgetallen vormen.

Arnout Jaspers voor NEMO Kennislink

Priemgetallen – gehele getallen die door geen enkel getal deelbaar zijn – hebben wiskundigen altijd gefascineerd. Het zijn in zekere zin de atomen van de rekenkunde; immers, uit de priemgetallen (2, 3, 5, 7, 11, 13, 17, 19, 23…) kun je door vermenigvuldiging alle overige gehele getallen maken. Er is nog nooit een deterministisch patroon ontdekt in hoe ze verspreid liggen tussen de overige getallen. Ook bestaat er, voor zover bekend, geen formule die alleen maar priemgetallen oplevert.

Daarom is het zoeken naar grote priemgetallen nog steeds iets wat veel wiskundigen en liefhebbers bezighoudt. De afgelopen twintig jaar heeft de Great Internet Mersenne Prime Search (GIMPS) telkens de nieuwe recordhouders geleverd. GIMPS omvat gratis downloadbare software die momenteel op duizenden computers naar nieuwe priemgetallen zoekt in de tijd dat ze stand-by staan. De nieuwste aanwinst, M77232917, een priemgetal van 23.249.425 decimale cijfers, is eind vorig jaar gevonden door een computer van Jonathan Pace, een 51 jaar oude elektrotechnisch ingenieur uit Germantown, Tennessee (Verenigde Staten).

Viervoudig gecheckt

Vervolgens is zijn claim op vier andere computersystemen geverifieerd, om uit te sluiten dat het hier om een computerbug gaat. Op 3 januari 2018 kwam de bevestiging dat M77232917 echt een priemgetal is. Pace deed al veertien jaar mee met GIMPS, en wint nu een prijs van drieduizend dollar voor zijn ontdekking.

De voortgang van de jacht op Mersenne-priemgetallen. Verticaal staat de exponent N van het Mersenne-priemgetal, dat altijd van de vorm 2N – 1 is.

Uitgelicht door de redactie

Economie
Je geld of je leven?

Maatschappijwetenschap
Politie, burgers en technologie-ontwikkelaars in gesprek over de toekomst van de stad

Informatica
De gigantische logistieke operatie van het coronavaccin

Steeds grotere Mersenne-getallen zijn heel makkelijk te maken en hebben allemaal dezelfde vorm: 2N – 1. In woorden: vermenigvuldig N getallen 2 met elkaar, en trek daar 1 vanaf. Als je een Mersenne-getal wilt vinden dat priem is, moet de exponent N in ieder geval priem zijn. De nu gevonden recordhouder M77232917 is 277.232.917 – 1, en inderdaad is 77.232.917 zelf ook een priemgetal.

Het is voor een computer een koud kunstje om zulke priemgetallen N van acht – of negen, of tien – cijfers te vinden. Maar het probleem is: dit is geen garantie dat het bijbehorende Mersenne-getal ook priem is. Dat zul je apart moeten checken, en omdat een Mersenne-getal met exponent N veel en veel groter is dan N zelf, duurt dit veel langer. En bijna altijd blijkt het Mersenne-getal dan toch geen priemgetal te zijn.

Efficiënte test

Niettemin beperkt de zoektocht naar extreem grote priemgetallen zich al decennia tot Mersenne-getallen, omdat er een redelijk snelle, efficiënte priemgetaltest bestaat, de Lucas-Lehmertest, die alleen voor Mersenne-getallen werkt. Voor een willekeurig getal van miljoenen cijfers is het ook voor de snelste computers onbegonnen werk om te testen of dit een priemgetal is.

Er is niet te voorspellen of een Mersenne-getal priem is, en de Great Internet Mersenne Prime Search houdt dus in, dat duizenden vrijwilligers en hun computers van zoveel mogelijk Mersenne-getallen checken of ze de begeerde eigenschap hebben. Het is dan ook puur toeval dat juist de computer van Price het vijftigste Mersenne-priemgetal vond.

Geen grootste priemgetal

Euclides bewees al 2500 jaar geleden dat er geen grootste priemgetal bestaat. Zijn bewijs is een wonder van eenvoud: stel, er bestaat wel een grootste priemgetal Q. Vorm dan het veel grotere getal P = (2 × 3 × 5 × 7 × ……x Q) +1, het product van alle priemgetallen tot en met Q, plus 1. Dan is P niet deelbaar door enig priemgetal kleiner of gelijk aan Q. Maar dan is P ofwel een priemgetal groter dan Q, of het heeft een priemdeler groter dan Q. In beide gevallen is er een tegenspraak met de aanname dat Q het grootste priemgetal is. Q bestaat dus niet. Dit betekent dat er oneindig veel priemgetallen zijn.

Overigens is nog niet helemaal zeker dat dit ook qua grootte het vijftigste Mersenne-priemgetal is. Tussen N = 37.156.667 (de exponent van het 45ste Mersenne priemgetal) en de N = 77.232.917 van deze nieuwe recordhouder liggen ruim twee miljoen priemgetallen, waarvoor nog niet in alle gevallen gecheckt is of die misschien ook een Mersenne-priemgetal opleveren.

Pure liefhebberij

Voor zover we nu kunnen overzien, heeft het zoeken naar zulke extreem grote priemgetallen geen nut. Het is pure liefhebberij. In de berichtgeving over de nieuwe recordhouder wordt soms gezegd dat grote priemgetallen nodig zijn voor het RSA-geheimschrift, dat onder meer het internetbankieren beveiligt.

Maar dat gebruikt priemgetallen van ‘maar’ een paar honderd cijfers; groot genoeg om RSA onkraakbaar te maken, maar klein genoeg om er snel mee te kunnen werken, zodat een internetbetaling geen uren hoeft te duren.

Dit artikel is een publicatie van NEMO Kennislink.
© NEMO Kennislink, sommige rechten voorbehouden
Dit artikel publiceerde NEMO Kennislink op 11 januari 2018

Discussieer mee

0

Vragen, opmerkingen of bijdragen over dit artikel of het onderwerp? Neem deel aan de discussie.

NEMO Kennislink nieuwsbrief
Ontvang elke week onze nieuwsbrief met het laatste nieuws uit de wetenschap.