Cookies op Tweakers

Tweakers maakt gebruik van cookies, onder andere om de website te analyseren, het gebruiksgemak te vergroten en advertenties te tonen. Door gebruik te maken van deze website, of door op 'Ga verder' te klikken, geef je toestemming voor het gebruik van cookies. Wil je meer informatie over cookies en hoe ze worden gebruikt, bekijk dan ons cookiebeleid.

Meer informatie

Gimps-project vindt langste priemgetal tot nu toe

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

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 2n - 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.

Door

Nieuwscoördinator

60 Linkedin Google+

Reacties (60)

Wijzig sortering
Is dit puur voor een melding in een of ander leaderboard of wordt hier ook daadwerkelijk wat mee bereikt ?
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 5 januari 2018 17:27]

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. O-)
+1 Omdat ik er ook wel om kon lachen. :)
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.
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.
Priemgetallen zijn ontzettend goede wachtwoorden/codes om iets te beveiligen
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 :)
Omdat je deze erg moeilijk kan ontbinden in factoren, en dat is wat wachtwoorden kraakprogramma's doen om wachtwoorden te kraken.

[Reactie gewijzigd door Maurits777 op 5 januari 2018 16:51]

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.
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)
Proficiat. Dat was mijn punt...
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.
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.
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 5 januari 2018 16:53]

Maar dit soort priemgetallen is daar veel te groot voor.
Nouja, direct als wachtwoord lijkt het me niet heel erg veilig. Mersenne priemgetallen zijn reeksen van binaire 1'tjes. :+
oeps...

[Reactie gewijzigd door Nystran op 6 januari 2018 13:43]

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. 8)7
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.
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 (264 ~= 0,5 miljoen; 265 ~= 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.
Oeps, mijn inschatting klopte van geen kanten.
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)
Dit is een Password Generator uit de toekomst!
Priemgetallen worden veelvuldig gebruikt voor encryptie (dus niet zozeer voor wachtwoorden, zoals eerder vermeld)

[Reactie gewijzigd door P1nGu1n op 5 januari 2018 16:47]

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.
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.
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);
En ik maar denken dat ze dit altijd met clusters deden maar het kan dus blijkbaar ook "gewoon" met een desktop.
GIMPS-project is in feite 1 groot cluster :)
De controle wel ja, dat duurt dus 6 dagen op een "gewone" desktop. Het vinden van het getal daar in tegen kan jaren duren.
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,
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.
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...
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 :p
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 :p
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?).
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
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 M77.232.917 en er zijn er slechts 7 kleiner dan 77.232.917 (de achtste zit daar ver boven: M31 = 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 M2.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[M9] = M2305843009213693951 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 2n - 1 priem te laten zijn moet n zelf ook priem zijn.
If n is a composite number then so is 2n − 1. (2ab − 1 is divisible by both 2a − 1 and 2b − 1.) This definition ["Mn = 2n − 1 for some integer n" - RvW] is therefore equivalent to a definition as a prime number of the form Mp = 2p − 1 for some prime p.

[Reactie gewijzigd door robvanwijk op 10 januari 2018 23:40]

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.
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.
De bevestiging is een stuk makkelijker uit te voeren. Een nieuw getal vinden daarentegen.
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)
Als je 6 dagen bezig bent per getal ben je wel even bezig.
Op een i5 was dat...

Als hij een 1070 had gebruikt?
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.
hoe wil je een rekensom waarbij telkens - 1 gedaan word versnellen op een gpu?
Valideren of het een priemgetal is.
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).
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 5 januari 2018 16:48]

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 7 januari 2018 22:40]

Vraag me af hoeveel er nog van z'n 3000$ overblijft als hij er de elektriciteitskosten van de afgelopen 14 jaar zoeken van aftrekt...
En dan heb je het nog niet over de hardware (upgrades/vervanging) over 14 jaar tijd.
mooie vondst! over een jaar weer eentje :P
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.
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. :P Dan wel met een nette OC natuurlijk, mooie test of het nog echt stabiel is :Y)

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! :X

[Reactie gewijzigd door Sugocy op 5 januari 2018 17:30]

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.


Call of Duty: Black Ops 4 HTC U12+ dual sim LG W7 Google Pixel 3 XL OnePlus 6 Battlefield V Samsung Galaxy S9 Dual Sim Google Pixel 3

Tweakers vormt samen met Tweakers Elect, Hardware.Info, Autotrack, Nationale Vacaturebank en Intermediair de Persgroep Online Services B.V. © 1998 - 2018 Hosting door True

*