Gimps-project vindt langste priemgetal tot nu toe

Een Amerikaanse vrijwilliger van het Gimps-project heeft het vijftigste bekende Mersenne-priemgetal gevonden. Het priemgetal 2^77,232,917-1 bestaat uit 23.249.425 cijfers en is daarmee bijna een miljoen cijfers groter dan de vorige recordhouder.

Marin Mersenne Het vijftigste bekende Mersenne-priemgetal is gevonden door de 51-jarige Amerikaan Jonathan Pace, die al veertien jaar meewerkt aan het Gimps-project en die drieduizend dollar verdient met zijn vondst. Het priemgetal met aanduiding M77232917 wordt verkregen door 2 tot de macht 77.232.917 te verheffen en er vervolgens 1 af te trekken.

Het gaat hierbij om een Mersenne-priemgetal: een priemgetal dat precies één kleiner is dan de macht van twee, ofwel 2ⁿ - 1. Dit soort priemgetallen zijn notoir moeilijk te vinden. Ze zijn vernoemd naar de Franse monnik Marin Mersenne, die ze 350 jaar geleden bestudeerde. Het Gimps-project is in 1996 in gang gezet en heeft de laatste zestien Mersenne-getallen gevonden. Het vorige dateert van januari 2016, toen een priemgetal van 22.338.618 cijfers gevonden werd.

Het bewijs is na zes dagen onafgebroken rekenen met de tool Prime95 gevonden op een pc met een Intel Core i5-6600. Daarna is het met de programma's gpuOwL op een AMD RX Vega 64 in 34 uur, CUDALucas op een Nvidia Titan Black-gpu in 73 uur, Mlucas op een Xeon-server in 82 uur en op een Amazon AWS-instance in 65 uur bevestigd.

IT-banen

Reacties (60)

m.diepenbroek 5 januari 2018 16:41

Is dit puur voor een melding in een of ander leaderboard of wordt hier ook daadwerkelijk wat mee bereikt ?

MneoreJ @m.diepenbroek • 5 januari 2018 17:25

Puur voor de patsfactor, basically.

In tegenstelling tot wat veel mensen hier aankaarten heeft het opzoeken van het grootste (Mersenne-)priemgetal geen praktische toepassing, ook niet voor cryptografie. Sterker nog, dit priemgetal is volkomen onbruikbaar voor dat doel omdat het publiek bekend is. By asymmetrische encryptie is de truc nu net dat je twee grote priemgetallen p en q genereert en het product p * q gebruikt, in de kennis (of liever gezegd de tot nu toe correct gebleken aanname) dat een aanvaller dit product niet makkelijk kan ontleden in factoren. Daarvoor moeten p en q wel geheim blijven, natuurlijk.

Zoals de FAQ van de site ooit zei (inmiddels lijkt het er niet meer op te staan):

Finding new Mersenne primes is not likely to be of any immediate practical value. This search is primarily a recreational pursuit. However, the search for Mersenne primes has proved useful in development of new algorithms, testing computer hardware, and interesting young students in math.

De getallen zelf zijn in zekere zin onbelangrijk, het gaat meer om het proces, en de aantrekkingskracht van "het grootst bekende priemgetal".

[Reactie gewijzigd door MneoreJ op 22 juli 2024 14:03]

TerraGuy @MneoreJ • 5 januari 2018 18:30

Puur voor de patsfactor, basically.

Ik las de titel van het artikel de eerste keer verkeerd, ik dacht dat het langste piemelgetal gevonden was. Nu ik bij jou lees dat de patsfactor nogal hoog is bij dit getal, klinkt 'langste piemelgetal' zo slecht nog niet.

BenVenNL @TerraGuy • 5 januari 2018 23:31

+1 Omdat ik er ook wel om kon lachen.

kidde @m.diepenbroek • 5 januari 2018 17:57

Dit is de voorloper van de bitcoin! Hier worden Mersenne priemgetallen gemined, in een gedistribueerd netwerk (waarin ook verificatie gedaan wordt). BTC is deels op dze technologie uit ca 1995 gebaseerd.

--Andre-- @kidde • 5 januari 2018 22:26

Wat dacht je dan van de PrimeCoin. Die zocht toch priemgetallen tijdens het minen? Destijds nog een tijdje gemined, maar die coin is niet echt succesvol gebleken.

Bozariusz @m.diepenbroek • 5 januari 2018 16:45

Priemgetallen zijn ontzettend goede wachtwoorden/codes om iets te beveiligen

m.diepenbroek @Bozariusz • 5 januari 2018 16:45

En waarom ?

MMaI @m.diepenbroek • 5 januari 2018 18:00

De belangrijkste reden waarom juist priemgetallen zo belangrijk zijn is dat ze zelf geen factoren hebben, waardoor je ze perfect als invoer kan gebruiken voor een sleutel generator. Als je namelijk een getal wat wel factoren heeft hiervoor gebruikt, kun je theoretisch ook één van de factoren gebruiken welke veelal veel eenvoudiger is. Daarmee is dan een aanval uit te voeren met behulp van de factoren in plaats van met de originele grote getallen.

Neem bijvoorbeeld als invoer 23 en 29, dan is je uitkomst voor een RSA sleutel altijd hetzelfde met 23 en 25. Neem je daarentegen 21 en 25 dan is je uitkomst hetzelfde als met 3 en 5, welke respectievelijk 7x en 5x eenvoudiger te berekenen zijn. Denk je nu in dat je getallen hebt die enkele seconden duren om te genereren, dan zou het duidelijk moeten zijn waar de priemgetallen voor nodig zijn

Bozariusz @m.diepenbroek • 5 januari 2018 16:51

Omdat je deze erg moeilijk kan ontbinden in factoren, en dat is wat wachtwoorden kraakprogramma's doen om wachtwoorden te kraken.

[Reactie gewijzigd door Bozariusz op 22 juli 2024 14:03]

ONiel @Bozariusz • 6 januari 2018 11:16

Zou je dit even verder kunnen uitleggen?
Priemgetallen worden gebruikt in cryptografie om data (zoals wachtwoorden) te beveiligen, maar hoezo is een priemgetal dan een goed wachtwoord?

"3571", dit is een priemgetal, waarom zou dit wachtwoord beter zijn dan "4822"?
Want toen ik voor het laatst checkte, werden wachtwoorden nog steeds gekraakt met dictionary-attacks of in sommige gevallen bruteforce-attacks.

En aangezien >99% van de wachtwoorden wel een karakter zoals "a", "b", of "$", bevatten, ben ik benieuwd hoe je het wachtwoord "abc123$" gaat kraken door te ontbinden in factoren.

woutv_ @ONiel • 8 januari 2018 08:44

Het gebruik van priemgetallen in het wachtwoord zelf is niet de bedoelde use case. Het gaat om priemgetallen als sleutel van het encryptie-algoritme, zoals bv in:https://nl.wikipedia.org/wiki/RSA_(cryptografie)

ONiel @woutv_ • 15 januari 2018 07:08

Proficiat. Dat was mijn punt...

m.diepenbroek @Bozariusz • 5 januari 2018 16:53

Okido, thanks voor de insight. Cryptografie is een onderwerp waarbij mijn kennis al snel te kort schiet vandaar dat ik ook niet wist dat priemgetallen hier veelal aan de basis liggen.

RoL0 @Bozariusz • 5 januari 2018 17:31

Dat is het punt: Je kunt ze niet ontbinden in factoren, dat is namelijk de definitie van een priemgetal. Encryptie maakt vaak gebruik van het product van twee (grote) priemgetallen, waarbij de twee orginele priemgetallen (die dus moeilijk te vinden zijn) gevonden moeten worden om de encryptie te kraken.

RoNoS @m.diepenbroek • 5 januari 2018 16:47

Cryptografie, bijvoorbeeld: https://nl.wikipedia.org/wiki/RSA_(cryptografie)

m.diepenbroek @RoNoS • 5 januari 2018 16:48

Check

Patrickkkk @m.diepenbroek • 5 januari 2018 16:50

asymetrische cryptografie gebruikt in o.a. de https sessie waarmee je naar tweakers en je bank etc. verbind maakt hier gebruik van.

uit de engelse versie

Its security is connected to the extreme difficulty of factoring large integers, a problem for which there is no known efficient general technique.

[Reactie gewijzigd door Patrickkkk op 22 juli 2024 14:03]

Alex3 @Bozariusz • 5 januari 2018 17:39

Maar dit soort priemgetallen is daar veel te groot voor.

Cilph @Bozariusz • 5 januari 2018 22:21

Nouja, direct als wachtwoord lijkt het me niet heel erg veilig. Mersenne priemgetallen zijn reeksen van binaire 1'tjes.

Nystran @Bozariusz • 6 januari 2018 13:40

oeps...

[Reactie gewijzigd door Nystran op 22 juli 2024 14:03]

Nystran @Bozariusz • 6 januari 2018 13:42

Priemgetallen zijn ontzettend goede wachtwoorden/codes om iets te beveiligen

Mijn wachtwoord is idd een priemgetal. Mensen mogen gerust meekijken als ik hem intoets, verder dan 8 van de 16 cijfers is niemand nog gekomen.

Milmoor

@Nystran • 7 januari 2018 09:29

Bedankt voor de password hint

. Ik verwacht dat er maar een heel beperkt aantal priemgetallen van 16 cijfers is. Hierdoor zou ik met deze info en de eerste paar cijfers jouw wachtwoord moeten kunnen afleiden.

robvanwijk

Wetenschap

@Milmoor • 7 januari 2018 20:38

Het lukt me niet om het exacte aantal priemgetallen tussen 1000000000000000 en 1000000100000000 (eerste acht cijfers bekend, laatste acht cijfers niet bekend) uit Wolfram Alpha te krijgen, maar bij benadering zijn het er een stuk of 2,8 miljoen. Ter vergelijking, de moeite om dat te kraken ligt tussen een password van vier en vijf kleine letters (26⁴ ~= 0,5 miljoen; 26⁵ ~= 11,8 miljoen).
Hoe groter de getallen worden, hoe kleiner de kans dat ze priem zijn; als iemand dus 99999999xxxxxxxx afgekeken heeft, dan maak je het nog makkelijker dan in het bovenstaande rekenvoorbeeld.

Milmoor

@robvanwijk • 7 januari 2018 21:00

Oeps, mijn inschatting klopte van geen kanten.

Nystran @robvanwijk • 10 januari 2018 22:23

$_/-\o_$ Respect! $_/-\o_$

badnews.nl @Nystran • 7 januari 2018 22:53

Moet je dan elke x maanden (verplichte password change) een nieuw priemgetal leren?

Maar een numeric password voldoet meestal niet aan de moderne eisen (hoodletter+kleine letter+leesteken+nummer en minimaal 8 tekens., dus slechts aan 2 van de 4 eisen)

Loggedinasroot @m.diepenbroek • 5 januari 2018 16:43

Dit is een Password Generator uit de toekomst!

P1nGu1n

@m.diepenbroek • 5 januari 2018 16:46

Priemgetallen worden veelvuldig gebruikt voor encryptie (dus niet zozeer voor wachtwoorden, zoals eerder vermeld)

[Reactie gewijzigd door P1nGu1n op 22 juli 2024 14:03]

Douweegbertje @m.diepenbroek • 5 januari 2018 17:37

In dit geval is het praktisch nut vrijwel nihil. Dit priemgetal gaat niet perse gebruikt worden, zeker niet voor bijv. encryptie.. daar is het domweg te groot voor EN hij is nu bekend. Nu is het onder het mom "omdat het kan". Uiteindelijk zit er altijd wat meer achter. Door te spelen en te blijven rekenen krijg je misschien in de toekomst meer nut met deze 'antwoorden'. Net zoals dat enorm veel mensen weer betrokken raken met priemgetallen voor andere doeleinden door dit soort nieuwsberichten.

Zoijar @m.diepenbroek • 5 januari 2018 17:59

Ze zijn ook nog nuttig voor error correcting codes, maar daar gebruiken we deze grote mersenne primes niet voor (wel kleinere, maar die hebben we dus al). De gehele getallen modulo 'x' wordt vaak als set (galois field) gebruikt voor handige error correcting properties, en als 'x' een mersenne prime is maakt het de berekeningen en stuk makkelijker... maar dat is nogal technisch.

Verder gebruiken we nog een mersenne prime voor random number generation in heel erg veel toepassingen (2^19937-1) Maar allemaal "kleine" dus.

laserve @m.diepenbroek • 6 januari 2018 10:46

Omdat de Mersenne twister machten van twee gebruikt wordt hij gebruikt voor een snel algoritme om random nummers te genereren. De primegetallen hebben de eigenschap dat ze goede random distributies genereren, het nadeel is alleen dat ze voorspelbaar zijn als je de basis prime weet. Bv de C++11 versie die gebruikt maakt van een vorige mersenne prime.

random_device device;
mt19937 generator(device());
uniform_int_distribution<int> distribution(1, 6);

int rnd = distribution(generator);

toekie 5 januari 2018 16:45

En ik maar denken dat ze dit altijd met clusters deden maar het kan dus blijkbaar ook "gewoon" met een desktop.

Robbierut4 @toekie • 5 januari 2018 17:22

GIMPS-project is in feite 1 groot cluster

NL-RaVeR @toekie • 5 januari 2018 16:57

De controle wel ja, dat duurt dus 6 dagen op een "gewone" desktop. Het vinden van het getal daar in tegen kan jaren duren.

Verwijderd 5 januari 2018 16:38

Het verbaasd me dat dit in slechts 6 dagen is berekend op een i5. Je zou toch verwachten dat iemand wel langer dan dat Prima95 heeft laten draaien? De investering is bijna niks,

RoNoS @Verwijderd • 5 januari 2018 16:46

Er zijn 1 miljoen priemgetallen tussen 67,867,979 en 86,028,121. Als je elke checkt en daarvan elke keer 6 dagen bezig bent, dan kan het wel even duren hoor.

FreezeXJ @RoNoS • 5 januari 2018 17:13

Gelukkig is stap 1 het sieven (zeven) van priemgetallen, waarmee je er al heel snel heel veel weg kunt smijten. De overgebleven getallen worden daarna (distributed) getest, en dat duurt inderdaad best lang...

JasperNLxD @FreezeXJ • 7 januari 2018 14:15

Tel daarbij op dat verreweg het grootste deel van Mersenne getallen die gecheckt zijn ook daadwerkelijk priem zijn. Als je dus gewoon een mersenne getal checkt gooi je dus waarschijnlijk al raak

robvanwijk

Wetenschap

@JasperNLxD • 7 januari 2018 20:25

Tel daarbij op dat verreweg het grootste deel van Mersenne getallen die gecheckt zijn ook daadwerkelijk priem zijn. Als je dus gewoon een mersenne getal checkt gooi je dus waarschijnlijk al raak

Ehm, waar haal je dat vandaan!? Een Mersenne priem is 2^n - 1. Als n zelf geen priem is, dan is 2^n - 1 automatisch ook geen priem, dus laten we je het voordeel van de twijfel geven en doen alsof de definitie 2^p - 1 is. Dan krijgen we:
2^2 - 1 = 3
2^3 - 1 = 7
2^5 - 1 = 31
2^7 - 1 = 127
2^11 - 1 = 2047 (niet priem: 23×89)
2^13 - 1 = 8191
2^17 - 1 = 131071
2^19 - 1 = 524287
2^23 - 1 = 8388607 (niet priem: 47×178481)
2^27 - 1 = 134217727 (niet priem: 7×73×262657)
Dus ja, in het begin ziet het er veelbelovend uit. Maar hoe verder je komt, hoe zeldzamer het wordt. Ga maar na, er zijn "wel wat meer" dan 50 priemgetallen tussen 2 en 77.232.917 (4.517.402 om precies te zijn; 50 van de 4,5 miljoen is niet echt "het grootste deel", toch?).

JasperNLxD @robvanwijk • 10 januari 2018 21:24

Excuus voor mijn late reactie.

Mijn gemaakte claim hierboven is "neem een mersenne getal, dan is deze met relatief hoge waarschijnlijkheid priem als je het vergelijkt met een andere eenvoudige serie". Ik zeg niet "neem een priem, is dit een mersenne getal", waarvan je goed aantoont dat die claim onjuist zou zijn.

Mijn reactie gaat over de priemdichtheid binnen de rij, niet over de volledigheid van de overdekking van de mersenne rij door priemen. Verder hoeft de exponent niet priem te zijn om een mersenne getal te zijn, een zijn er genoeg mersenne priemen met een niet-priem exponent

robvanwijk

Wetenschap

@JasperNLxD • 10 januari 2018 23:40

Mijn gemaakte claim hierboven is "neem een mersenne getal, dan is deze met relatief hoge waarschijnlijkheid priem als je het vergelijkt met een andere eenvoudige serie". Ik zeg niet "neem een priem, is dit een mersenne getal", waarvan je goed aantoont dat die claim onjuist zou zijn.

Dat vind ik een beetje een lastige claim...

Ten eerste moet het zijn "neem een Mersenne priem" (niet zomaar een Mersenne getal, zie antwoord op het tweede deel van je post). Maar met die aanpassing: Mersenne priemgetallen groeien zeer snel; het grootste Mersenne priemgetal is M_77.232.917 en er zijn er slechts 7 kleiner dan 77.232.917 (de achtste zit daar ver boven: M₃₁ = 2.147.483.647 ja inderdaad, dat is MaxInt). Van die zeven heb je vier keer gelijk (3, 7, 31, 127), maar de volgende drie (8191, 131071, 524287) gaan allemaal mis.

Ik heb geen flauw idee of er een speciale reden is om aan te nemen dat M_{2.147.483.647} waarschijnlijk wel of juist waarschijnlijk niet priem is, maar ik vrees dat we nog wel even op het resultaat zullen moeten wachten. En daarna is je claim meteen betekenisloos, want ik verwacht niet dat we het moment nog mee gaan maken waarop vastgesteld wordt of M[M₉] = M_{2305843009213693951} priem is of niet.

Verder hoeft de exponent niet priem te zijn om een mersenne getal te zijn, een zijn er genoeg mersenne priemen met een niet-priem exponent

Nee, om 2ⁿ - 1 priem te laten zijn moet n zelf ook priem zijn.

quote: https://en.wikipedia.org/wiki/Mersenne_prime
If n is a composite number then so is 2ⁿ − 1. (2^ab − 1 is divisible by both 2^a − 1 and 2^b − 1.) This definition ["M_n = 2ⁿ − 1 for some integer n" - RvW] is therefore equivalent to a definition as a prime number of the form M_p = 2^p − 1 for some prime p.

[Reactie gewijzigd door robvanwijk op 22 juli 2024 14:03]

marcmeide @Verwijderd • 5 januari 2018 16:41

Volgens mij gaat het hier om een bevestiging, en niet een zoek actie naar deze prime. Er is dus specifiek gecontroleerd of dit getal prime is. op een 6600 zou het dus per getal om te controleren (in de zelfde order of magnitude) ongeveer 6 dagen kosten.

slowdive @marcmeide • 5 januari 2018 17:39

Het gaat om de zoekactie én de bevestiging.
Het priemgetal is gevonden met een zoekactie en daarna op andere computers met andere implementaties van hetzelfde algoritme gecontroleerd.
Het zoeken is zeer intensief omdat de kans zeer klein is dat een willekeurig getal van deze grootte priem is.
Waarschijnlijk zijn op dit moment nog niet alle Mersenne-getallen getallen kleiner dan het record gecontroleerd. In theorie kan daar dus ook nog een priemgetal tussenzitten.

TacoE @Verwijderd • 5 januari 2018 16:40

De bevestiging is een stuk makkelijker uit te voeren. Een nieuw getal vinden daarentegen.

totaalgeenhard @TacoE • 5 januari 2018 17:06

Willekeurig cijfer met miljard cijfers en vervolgens er telkens 1 vanaf trekken... vroeg of laat heb je een priem getal.

(denk er eens over na indien je het niet met me eens bent)

i7x @totaalgeenhard • 5 januari 2018 17:09

Als je 6 dagen bezig bent per getal ben je wel even bezig.

totaalgeenhard @i7x • 5 januari 2018 17:37

Op een i5 was dat...

Als hij een 1070 had gebruikt?

Nogne @totaalgeenhard • 5 januari 2018 18:35

Nvidia Titan Black-gpu in 73 uur

Ik weet niet hoeveel sneller een Titan Black is, maar die i5 doet het nog niet zo slecht.

aadje93 @totaalgeenhard • 9 januari 2018 19:12

hoe wil je een rekensom waarbij telkens - 1 gedaan word versnellen op een gpu?

totaalgeenhard @aadje93 • 9 januari 2018 23:28

Valideren of het een priemgetal is.

FreezeXJ @totaalgeenhard • 5 januari 2018 17:11

Ah, waarschijnlijk wordt dat laat dan... De dichtheid aan priemgetallen neemt langzaam maar zeker af, en het testen wordt steeds lastiger.
Dat is ook precies de reden dat we nu Mersenne-getallen testen, want dat is makkelijker dan een random getal (lang leve binair, waarin een Mersenne-priem vertegenwoordigd is door een hele sloot 1en).

Rolf @Verwijderd • 5 januari 2018 16:48

Er zijn veel Mersenne getallen die priem zouden kunnen zijn (2^x -1, met x een priemgetal) maar slechts weinigen ervan zijn priem. Ik neem aan dat deze PC gewoon begonnen is aan de volgende kandidaat en toen in 5 dagen vond dat het priem was. Daarna laat je het een paar keer narekenen.

[Reactie gewijzigd door Rolf op 22 juli 2024 14:03]

Jack Flushell

@Verwijderd • 7 januari 2018 22:39

Lees anders even na waarover dit precies gaat... Hij is al 14 jaar aan het zoeken. De berekening / controle van dit specifieke getal duurde 6 dagen nogwat.

[Reactie gewijzigd door Jack Flushell op 22 juli 2024 14:03]

craio 5 januari 2018 18:16

Vraag me af hoeveel er nog van z'n 3000$ overblijft als hij er de elektriciteitskosten van de afgelopen 14 jaar zoeken van aftrekt...

BackBones @craio • 6 januari 2018 09:18

En dan heb je het nog niet over de hardware (upgrades/vervanging) over 14 jaar tijd.

Verwijderd 5 januari 2018 16:46

mooie vondst! over een jaar weer eentje

rbr320 @Verwijderd • 5 januari 2018 17:11

De vorige vondst was in januari 2016, het is nu januari 2018. Dus het lijkt me logisch dat de volgende pas over 2 jaar gevonden gaat worden. En aangezien het niet lineair schaalt vermoed ik dat het nog wel langer gaat duren.

Sugocy 5 januari 2018 17:26

Was dat met die i5 voor of na de spectre/meltdown patch?

Zou bijna mijn eigen 6600 aan het rekenen willen zetten, maar doe gelukkig meer met mijn pc dus vertrouw ze maar.

Dan wel met een nette OC natuurlijk, mooie test of het nog echt stabiel is

Iemand enig idee hoe je dat in prime95 doet? *gaat googlen*

Edit: onder advanced tab zitten meerdere opties!

Kijk ik ook een keer verder dan torture!

[Reactie gewijzigd door Sugocy op 22 juli 2024 14:03]

HolaGanz @Sugocy • 5 januari 2018 19:13

Was dat met die i5 voor of na de spectre/meltdown patch?

Zal niet veel uit moeten maken, de patches vertragen voornamelijk kernel calls die bij Prime95 waarschijnlijk bijna niet gebruikt worden aangezien het vooral om keihard rekenen gaat.

Op dit item kan niet meer gereageerd worden.

Gimps-project vindt langste priemgetal tot nu toe

Lees meer

IT-banen

Reacties (60)

Sorteer op:

Weergave: