Grootste bekende priemgetal ontdekt: waarom het ertoe doet

In de film Contact, gebaseerd op de gelijknamige roman van Carl Sagan, zoekt Dr. Ellie Arroway naar intelligent buitenaards leven door de lucht af te tasten met radiotelescopen. Wanneer Arroway, gespeeld door Jodie Foster, priemgetallen herkent in een interplanetair signaal, gelooft ze dat dit het bewijs is dat een buitenaardse intelligentie de mensheid een bericht heeft gestuurd.

Een getal wordt als priemgetal beschouwd als het alleen deelbaar is door een en zichzelf. Twee, drie, vijf en zeven zijn bijvoorbeeld priemgetallen. Het getal 15, dat drie keer vijf is, is geen priemgetal. Het is geen toeval dat Arroway gelooft dat de aliens in Contact priemgetallen gebruiken als een kosmische “hallo” – het zijn bouwstenen van andere getallen. Elk getal is een product van priemgetallen.

In december 2017 de grootste bekende priemgetal werd ontdekt met een computerzoekopdracht. Het priemgetal werd ontdekt door Jonathan Pace, een elektrotechnisch ingenieur die momenteel bij FedEx werkt. Waarom is dit belangrijk? Omdat zonder priemgetallen uw bankgegevens, Paypal-transacties of Amazon-aankopen in gevaar kunnen komen.

Grote priemgetallen, zoals degene die zojuist is ontdekt, spelen een cruciale rol in cyberbeveiliging. Cryptografie is de wetenschap van het coderen en decoderen van informatie, en veel van zijn algoritmen, zoals RSA, zijn sterk afhankelijk van priemgetallen.

Mersenne priemgetallen

Hoewel er oneindig veel priemgetallen zijn, is er geen f ormula om ze allemaal te genereren. Er is een race gaande om grotere priemgetallen te vinden met behulp van een combinatie van wiskundige technieken en berekeningen.

Een manier om grote priemgetallen te krijgen, maakt gebruik van een wiskundig concept dat is ontdekt door de 17e-eeuwse Franse monnik en geleerde, Marin Mersenne.

Een Mersenne-priemgetal is een van de vorm 2ⁿ – 1, waarbij n een positief geheel getal is. De eerste vier hiervan zijn drie, zeven, 31 en 127.

Niet elk getal van de vorm 2ⁿ – 1 is echter een priemgetal; bijvoorbeeld 2⁴ – 1 = 15. Als 2ⁿ – 1 een priemgetal is, dan kan worden aangetoond dat n zelf een priemgetal moet zijn. Maar zelfs als n een priemgetal is, is er geen garantie dat het getal 2ⁿ – 1 een priemgetal is: 2¹¹ – 1 = 2047, wat geen priemgetal is omdat het gelijk is aan 23 keer 89.

Er zijn slechts 50 bekende Mersenne priemgetallen . Een onopgelost vermoeden is dat er een oneindig aantal is.

De zoektocht naar nieuwe prime-lenzen

The Great Internet Mersenne Prime Search (of GIMPS) is een gezamenlijke inspanning van veel individuen en teams van over de hele wereld om nieuwe Mersenne-prime-lenzen te vinden. George Woltman begon met GIMPS in 1996, en in 2018 omvat het meer dan 183.000 vrijwillige gebruikers die bijdragen aan de collectieve kracht van meer dan 1,6 miljoen CPUs.

De meest recent ontdekte Mersenne prime is bondig geschreven als 2⁷⁷²³²⁹¹⁷ – 1; dat is twee 77.232.917 keer met zichzelf vermenigvuldigd, min één. De ontdekking van Jonathan Pace nam zes dagen berekening in beslag op een quad-core Intel i5-6600 CPU en werd onafhankelijk geverifieerd door vier andere groepen.

De nieuw ontdekte prime heeft maar liefst 23.249.425 cijfers. Om een idee te krijgen van hoe groot dat is, stel dat we een boek vullen met cijfers, elk cijfer wordt geteld als een woord en elk boek 100.000 woorden. Dan zouden de cijfers van 2⁷⁷²³²⁹¹⁷ – 1 ongeveer 232 boeken vullen!

Hoe vindt GIMPS priemgetallen?

GIMPS gebruikt de Lucas-Lehmer-test voor priemgetallen. Vorm hiervoor een reeks gehele getallen beginnend met vier, en waarvan de termen de vorige term in het kwadraat zijn en min twee. De test zegt dat het getal 2ⁿ – 1 een priemgetal is als het de (n-2) de term in de reeks deelt.

Hoewel de Lucas-Lehmer-test eenvoudig genoeg lijkt om te controleren, is de computationele bottleneck bij het toepassen het komt van kwadraatgetallen. Vermenigvuldiging van gehele getallen is iets wat elk schoolkind kan doen, maar voor grote getallen levert het problemen op, zelfs voor computers. Een manier om dit te omzeilen is door Fast Fourier Transforms (FFT) te gebruiken, algoritmen die berekeningen versnellen.

Iedereen kan meedoen met GIMPS – zolang je een fatsoenlijke computer met een internetverbinding hebt. Gratis software om te zoeken naar Mersenne-priemgetallen is te vinden op de GIMPS-website.

Hoewel het grootste bekende priemgetal verbluffend groot is, zijn er oneindig veel meer priemgetallen die wachten om ontdekt te worden. Net als Ellie Arroway deed in Contact, hoeven we ze alleen maar te zoeken.