Gimps-project vindt 48ste Mersenne-priemgetal

Een vrijwilliger van het distributed computing-project Gimps heeft het achtenveertigste Mersenne-priemgetal, met een lengte van 17.425.170 cijfers, gevonden. Het getal is daarmee het langste priemgetal dat op dit moment bekend is.

De vrijwilliger is Curtis Cooper, professor aan de universiteit van Central Missouri. Het is het derde Mersenne-priemgetal dat hij met de universiteitscomputers heeft gevonden. De andere twee priemgetallen vond hij in 2005 en 2006. Deze Mersenne-priemgetallen zijn een speciale klasse van priemgetallen: machten van twee, minus één. Van deze getallen zijn er tot nu toe slechts achtenveertig gevonden. Het vorige Mersenne-priemgetal werd gevonden in 2009.

Voor het vinden van deze getallen wordt gebruik gemaakt van computers van vrijwilligers en universiteiten. Het distributed computing-project dat zoekt naar Mersenne-Priemgetallen noemt zich GIMPS, een afkorting voor Great Internet Mersenne Prime Search. Dit zeventien jaar oude project gebruikt op dit moment meer dan 360.000 cpu's met pieken van 150 biljoen berekeningen per seconde.

Voor de vondst van 2^57.885.161-1 is een beloning uitgereikt van 3000 dollar. Het project heeft als volgende doelstelling om als eerste een priemgetal van meer dan 100 miljoen cijfers te vinden, om zo de prijs van 150.000 dollar op te kunnen strijken, uitgereikt door de Electronic Frontier Foundation. Wie een Mersenne-priemgetal met een miljard cijfers vindt, kan zelfs rekenen op een prijs van 250.000 dollar.

Reacties (78)

[Anoniem: 203642]

Aan eenieder die zoekt naar praktisch nut.... tsjonge jonge zeg. Omdat het KAN! Dat moet een Tweaker toch aanspreken?

Maar er is nog een betere reden. De benodigde algoritmen en software implementaties zijn "State of the art" en de ontwikkelingen gebeuren veelal in of dichtbij dat project. Die ontwikkelingen en codes vinden genoeg toepassingen voor praktische toepassingen. Bijvoorbeeld assembly tweaks om snel een multiplicatie van grote getallen te kunenn doen, op alle mogelijke processor architecturen -- het is een distributed project heh.

[edit]
Oh ja nog iets. Er bestaan wat gekke wiskundige stellingen / observaties gerelateerd aan deze zeldzame getallen. Het uitbreiden van de dataset kan leiden tot nieuwe inzichten - of het blijkt dat een aanname niet meer klopt voor de nieuwste toevoeging (de 48e in dit geval), of het statistische bewijs wordt steeds sterker en de wetenschappers worden getart om het vraagstuk nou eindelijk eens op te lossen.
In de wiskunde zijn dwarsverbanden van het ene veld naar het andere soms verrassend en heel soms met grote gevolgen. Misschien hier eens lezen?
http://primes.utm.edu/mersenne/NewMersenneConjecture.html

[edit tenslotte]
Hier een veel betere en leukere uitleg dan ik kan geven.
http://primes.utm.edu/notes/faq/why.html

[Reactie gewijzigd door Anoniem: 203642 op 23 juli 2024 22:07]

[Bundin]

Dan liever dat de clockcycles worden ingezet voor medical research. Er zijn distributed computer projects die nuttiger zijn dan het vinden van een bizar groot getal "omdat het kan".

[Graviton12]

Kunnen ze hier niet iets voor schrijven dat adhv de eerder gevonden Mersenne getallen op zoek gaat naar een overeenkomst en hierop gaat zoeken ipv elk priem getal af te gaan?

[Anoniem: 157299]

Op zich is de reden dat er naar mersenne priemgetallen wordt gezocht natuurlijk al dat er bepaalde eigenschappen van deze priemgetallen zijn waardoor ze makkelijker te vinden zijn dan andere priemgetallen

http://en.wikipedia.org/w...0%93Lehmer_primality_test

En ze zullen vast ook bezig zijn met deze priemgetallen beter te begrijpen, maar het lijkt me dat ze op dit moment dus nog niet meer weten dan het gene wat GIMPS nu gebruikt.

Het is ook erg onwaarschijnlijk dat er een algoritme zou bestaan wat direct alle getallen van deze vorm die priem zijn op zou noemen.

[Upquark]

Nee. Men dacht wel ooit dat indien 2^n-1 een priemgetal is, dat 2^(2^n-1)-1 dat ook is, maar helaas, 2^8191-1 is niet priem.

[Trasos]

Dat 2^n-1 een priemgetal is kunnen ze nooit heel lang gedacht hebben.
2^4-1 is 15 en geen priemgetal.

Edit:
Ik zie nu pas de "indien" staan...

[Reactie gewijzigd door Trasos op 23 juli 2024 22:07]

[Pseud0n]

Alle Mersenne-priemen zijn 2^n -1, dat wil echter niet zeggen dat 2^n -1 steeds een priem is, anders hadden we alle Mersenne-priemen reeds binnen handbereik.

Men dacht echter dat ALS 2^n-1 een priem is, 2^(2^n -1) -1 ook een priem was. De als is hier natuurlijk wel belangrijk

[revertive]

We doen met zijn alle wel vaker dingen die uiteindelijk een stuk maklelijker opgelost hadden kunnen worden, dus zo raar is deze vraag niet.

[Seal64]

Zoals men wel eens zegt:

"Achteraf kijk je de koe in haar kont."

Negen van de tien keer blijkt inderdaad dat het makkelijker had gekund, maar wordt die manier alleen gevonden op basis van de data die je met de moeilijke manier verzameld hebt.

[Anoniem: 469193]

Iedereen vraagt hier zich af waarvoor dit nou praktisch nut zou hebben,
Maar heeft dan niemand aan de RSA-encrypty gedacht?
Met zo'n groot priemgetal kunnen ze over 100000000 jaar nog steeds je bericht niet ontsleutelen.

[Upquark]

Nee. Voor encryptie zijn deze priemgetallen niet bruikbaar, sowieso niet vanwege de grootte en al helemaal niet omdat dit een bekend priemgetal is. Dat wil je juist niet.

[i-chat]

wat een onzin... net alsof er onbekende priemgetallen zijn...

elke hacker met een beetje bot net zou zo een lijstje kunnen doorrekenen met priemgetallen ....

het gaat er bij encryptie om dat 'de kraker niet weet, en niet kan raden welke van alle honderden zo niet duizenden premgetallen er exact gebruikt zijn...

net als dat je elk password gewoon kan raden, in het makkelijkste geval zijn er maar 36 mogelijkheden per digit, soms komen daar nog het . punt en het - streepje bij... maar zelden worden ook overige 'lees'-tekens ondersteund...

even voor jouw informatie: de enige redelijk haalbare manier om erachter te komen welk primgetal er gebruikt is, is het hele document proberen te decrypten en kijken of er iets leesbaars uit komt... als je dat een paar honderd miljoen keer moet doen, heb je onrealistisch veel cpu kracht nodig, en DAT is nu juist de kracht van encryptie..

[Reactie gewijzigd door i-chat op 23 juli 2024 22:07]

[EnnaN]

wat een onzin... net alsof er onbekende priemgetallen zijn...

Ten eerste: het lijkt me duidelijk dat er onbekende priemgetallen zijn. Dat zijn alle priemgetallen groter dan deze die net gevonden is (en die bestaan want euclides bewees al dat er oneindig veel zijn als ik het me goed herinner). Dus ja, er zijn onbekende priemgetallen.

Verder lijkt het me logisch om net als het niet nemen van '0000' als pincode, niet deze ene edge-case te nemen voor al je cryptografische toepassingen. Er zijn namelijk meer betekenissen van het woord "bekend". Je hebt bekend als in "we weten van het bestaan" en je hebt ook de variant "iedereen denkt aan dit getal". En in dat geval hoef je dus niet een 'paar honder miljoen keer' iets te doen, maar doe je een soort dictionary-attack.

Als laatste: hoezo deze zin:

maar zelden worden ook overige 'lees'-tekens ondersteund...

Dat is niet mijn ervaring. Sterker nog, ik gebruik behoorlijk vaak andere leestekens in wachtwoorden.

[Reactie gewijzigd door EnnaN op 23 juli 2024 22:07]

[Anoniem: 157299]

>> even voor jouw informatie: de enige redelijk haalbare manier om erachter te komen welk primgetal er gebruikt is, is het hele document proberen te decrypten en kijken of er iets leesbaars uit komt... als je dat een paar honderd miljoen keer moet doen, heb je onrealistisch veel cpu kracht nodig, en DAT is nu juist de kracht van encryptie..

Dit is niet waar. Het geldt misschien wel voor veel andere encryptie methoden, maar bij RSA is het in principe mogelijk de precieze twee priemgetallen te achterhalen, zonder dat je de inhoud van het bericht hoeft te raadplegen. Je weet namelijk het product van 2 priemgetallen, en als het je lukt dit product te ontbinden, dan heb je alle informatie die nodig is om je bericht te decoden.

De reden waarom RSA trouwens als veilig wordt gezien is dat het omgekeerde ook geldt. Als je het gedecodeerde bericht hebt heb je ook informatie waarmee het relatief makkelijker is het oorspronkelijke getal te ontbinden, maar omdat het ontbinden van getallen iets is waar al enorm veel wiskundig onderzoek naar gedaan is, en waar over het algemeen de verbeteringen met kleine stappen gaan, gaat men er vanuit dat er niet snel iemand een manier zal vinden om RSA te kraken die snel genoeg is om bruikbaar te zijn.

[Reactie gewijzigd door Anoniem: 157299 op 23 juli 2024 22:07]

[Anoniem: 431208]

ja maar dan moet je priemgetal wel geheim zijn...

[90710]

Wel jammer dat Tweakers niet het gehele getal in het nieuwsbericht toont.

[Mijzelf]

Het gehele getal staat er: 2^57.885.161-1. Als je het helemaal uitgeschreven wilt hebben is deze pagina zomaar 17MiB groot. Vindt de server niet echt leuk denk ik.

[90710]

Dat klopt wel, maar het neemt niet weg dat ik het jammer vind

Je kan het getal trouwens hier downloaden:
http://www.isthe.com/chon...5161/huge-prime-c.html.gz

"maar" 9,6 MB

[Reactie gewijzigd door 90710 op 23 juli 2024 22:07]

[Durandal]

Of je download de gecomprimeerde versie hier, van maar 12 bytes:
2^57.885.161-1

[.oisyn]

Heel simpel, in binaire notatie zijn het gewoon 57.885.161 éénen achter elkaar.

[DVDL]

Wel leuk dat dit soort computing echt tot resultaten leid. Maar om even simpel te zeggen, wat heb je er nou aan om van dit soort getallen het bestaan te weten?
Verder zou ik liever m'n geld in zetten op onderzoek naar ziekte's en dat soort dingen, als je dan toch je CPU/GPU aan het maxen bent.. http://www.worldcommunitygrid.org/

[.ScorpionSquad]

Ik heb wel eens gehoord dat bijvoorbeeld de CIA priemgetallen gebruikt voor codering. Met zo'n grote en met een speciale eigenschap kan je vast wel iets.

[Diumelia]

Klopt. Vroeger, en dan heb ik het vooral over oorlogstijden, werden priemgetallen ook al gebruikt om (belangrijkere) berichten te versleutelen omdat deze dan moeilijker te kraken waren.

Maar ik zie ook niet echt het nut van dergelijke grote priemgetallen.

[Anthirian]

Het nut van dusdanig grote priemgetallen komt naar voren in onder meer RSA-cryptografie. De encryptiesleutel is gebaseerd op twee "voldoende grote" priemgetallen. Hoe lager de priemgetallen, hoe gemakkelijker de sleutel te raden is. Het is dus van belang om de priemgetallen groot te kiezen voor het genereren van een veilige sleutel.

Voor een basale uitleg verwijs ik je naar Wikipedia: http://en.wikipedia.org/wiki/RSA_(algorithm)

[Nactive]

Dit priem getal heeft zover ik weet geen enkel nut op RSA. RSA gebruikt priemgetallen, maar deze priemgetallen mogen niet makkelijk achterhaald worden. Dus je bent niks met dit priemgetal.

Het enigste waar ze het misschien voor kunnen gebruiken om zwak heden in priem getallen te vinden, maar dan nog betwijfel ik dat ze dit hiermee heel veel zijn.

IK betwijfel dan ook dat de onderzoekers alleen maar achter het Marssene priemgetal zoeken. Ze zullen waarschijnlijk ook nog andere priemgetallen onderzoeken en ook de Marsenne priemgetallen in hun onderzoek gebruiken.

[Seal64]

Alle priemgetallen die voor RSA gebruikt zouden kunnen worden, zijn per definitie bekend, en dus - theoretisch althans - "gemakkelijk achterhaalbaar". Je zou gewoon een lijstje kunnen opstellen waar alle bekende priemgetallen op staan.

Zelfs als ik dit zou gebruiken voor RSA, dan moet jij nog maar zien aan te tonen dat ik specifiek dit priemgetal gebruikt heb. Succes daarmee.

[Anoniem: 157299]

Het is voor een niet al te groot getal relatief niet zo moeilijk om te bepalen of het een priem getal is. Bij RSA kies je dus twee priemgetallen uit die nog binnen een bereik liggen waarbij het te bepalen is of ze priem zijn (en omdat de kans dat een getal een priemgetal best groot is, is het heel goed te doen om gewoon willekeurige getallen te blijven kiezen, en dan te controleren of ze priem zijn). Het product van deze twee priem getallen is dan natuurlijk al een heel stuk groter dan de priemgetallen zelf, maar het probleem is dan niet meer bepalen of een bepaald getal wel of niet een priemgetal is, maar de precieze twee priemfactoren van dit grotere getal vinden. Alle producten van twee priemgetallen in een bepaald bereik uitproberen is zowiezo al veel te veel werk, maar zelfs de rekenkracht die nodig is bij slimmere manieren om een getal N te ontbinden is veel hoger dan de rekenkracht die nodig is om twee priemgetallen te vinden die rond de sqrt(N) liggen.

[MSalters]

Haha, nee. De overgrote meerderheid van getallen is geen priem. Dat lijkt zo omdat onder kleine getallen de priemgetallen oververtegenwoordigd zijn. Onder de duizend is 1 op de 7 getallen priem, onder de 10 miljard is dat al gedaald tot 1 op de 23. Maar voor crypto gebruik je getallen van 100 cijfers of meer, en dat betekent dat minder dan 1 op de duizend getallen priem is.

[Anoniem: 157299]

Het overgrote deel van de getallen is idd geen priem, maar ze zijn ook niet echt bepaald zeldzaam. De kans dat een willekeurig getal n priem is, is ongeveer 1/ln n, wat dus betekend dat als je een priemgetal in de buurt van n wilt vinden, je er na ln n pogingen meestel wal een gevonden zult hebben. Rond de miljard is dit dus 1 op de 20. Best groot is natuurlijk niet echt duidelijk gedefinieerd, maar persoonlijk vind ik 1 op de 20 rond de miljard best groot:).

Een willekeurig getal kiezen, testen of het priem is, en zoniet het volgende getal proberen, totdat een priem gevonden is (eventueel nog met wat zeving om veelvouden van de kleine priemgetallen eruit te halen), is toch echt een veel gebruikte manier om priemgetallen voor RSA te kiezen.

[Munters]

Zeving van veelvouden van kleine priemgetallen? Als je een priemgetal hebt, is die per definitie geen veelvoud van een kleiner priemgetal.

[trogdor]

zwakheden in priemgetallen? wat zijn dat?

[Nactive]

Indien je bepaalde priemgetallen gebruikt met bepaalde eigenschappen kan door analyse eenvoudiger als andere priemgetallen de priemgetallen achterhaald worden.

Voor RSA worden dan niet zomaar 'ale grote priemgetallen gebruikt' maar priemgetallen met bepaalde eigenschappen. Ik weet de eigenschappen nu niet direct meer maar onder andere mogen u twee priemgetallen niet te dicht bji elkaar liggen.

Hier heb je een hele uitleg over het kiezen van priemgetallen voor gebruik bij RSA: http://www.rsa.com/rsalabs/node.asp?id=2217

[Nactive]

Priemgetallen worden inderdaad voor codering gebruikt. Maar die moeten juist zo random mogelijk zijn (en aan nog wel wat eigenschappen voldoen) zodat ik niet kan weten welk priemgetal je gebruikt ...

[WaterFire]

Tja, en als je er dan 48 hebt om uit te kiezen kunnen zelfs wij die kraken

[Echt niet.]

Maar als er dan miljoenen pc's meedoen met dit project, hoe kan je dan bepalen wie het getal gevonden heeft? Is dit gewoon de nerd-versie van de postcode loterij?

[Pyrus]

Ieder getal wordt door één persoon (soms twee, in ieder geval bij PrimeGrid) getest. De projectleiding weet dus precies wie welk getal test. Daardoor kunnen ze stellen $persoon heeft het getal gevonden. Wie nou toevallig dat ene getal toebedeeld krijgt dat priem blijkt te zijn, dat is wel compleet willekeurig. Als die knakker een minuut eerder of later een nieuw getal opgevraagd had om te testen, dan had iemand anders deze gehad.

[ZpAz]

Hoelang is een thuiscomputer dan bezig met het controleren van één getal of deze priem is of niet? (Ongeveer? Bij een even getal ben je al snel klaar ).

Want als dat erg lang duurt, laat je dan één getal dan maar door één computer berekenen? Of zet je er meerdere op, indien dat laatste, wie is dan de winnaar?

[Upquark]

Omdat elk getal maar een keer tegelijk wordt uitgedeeld. Ik meen dat alles wel dubbel getest wordt, maar het is sowieso duidelijk wie het priemgetal uiteindelijk gevonden heeft.

[i-chat]

dus idd een loterij

[Anoniem: 454685]

Serieuze vraag: wat is hier het praktisch nut van?

[Anoniem: 431208]

als je wiskunde beoefent, denk je niet altijd: waar ga ik dit voor gebruiken? het is een soort van hobby. ik vind priemgetallen zelf ook interessant dus dit soort 'ontdekkingen' vind ik altijd leuk.

[DrVic]

Ik denk dat de normale verwarming al een paar jaar stuk is bij die uni, ik kan verder niets verzinnen

[VictordeHolland]

Voor alle mensen die zich afvragen waar priemgetallen nuttig voor zijn: encryptie.
Het RSA algorithme maakt bijvoorbeeld gebruik van priemgetallen.

[i-chat]

dat zijn lang niet allemaal mercene primes...

de vraag was dus niet wat het nu was van priem in het algemeen, maar wat het nut is van, uit te zoeken of een bepaalde priem toevallig ook nog mercene is...

[Martindo]

Erg leuk dat dit priemgetal wordt gevonden, maar ik vraag me toch altijd af wat voor nut het nog heeft om zulke grote getallen te vinden. In wat voor situaties dien je een dergelijk priemgetal te gebruiken?

[Nactive]

Wat ik mij afvraag, voor wat is dit nuttig.

Ik snap wel het nut van priemgetallen e.d. Maar wat zijn we meer met het 48ste Mersenne-priemgetal te vinden?