Gimps-project vindt Mersenne-priemgetal van 12 miljoen cijfers

Een distributed computing-project dat als doel heeft zogenoemde Mersenne-priemgetallen te vinden, heeft een Cooperative Computing Award van de EFF toegewezen gekregen voor het vinden van een priemgetal met twaalf miljoen cijfers.

Het distributed computing-project dat voor het zoeken naar de grote priemgetallen verantwoordelijk is, noemt zich GIMPS, een afkorting voor Great Internet Mersenne Prime Search. Het zoeken naar grote priemgetallen betekent in de praktijk vaak een zoektocht naar Mersenne-priemgetallen, waarvan er nog geen vijftig bekend zijn. Deze speciale priemgetallen worden gevormd door een getal dat een macht van 2 is, min 1. Het door GIMPS gevonden Mersenne-priemgetal bestaat uit twaalf miljoen getallen en het is het vijfenveertigste Mersenne-priemgetal.

Voor het vinden van 2^43.112.609 -1 ontving het GIMPS-project een beloning van honderdduizend dollar, uitgereikt door de Electronic Frontier Foundation. Het geld zal gaan naar de wiskunde-faculteit van de UCLA, dat 50.000 dollar krijgt, terwijl 25.000 naar liefdadigheid gaat en het resterende bedrag benut zal worden om verder onderzoek te bekostigen en om deelnemers aan de zoektocht te belonen.

De EFF looft een beloning uit van 150.000 dollar voor het vinden van een Mersenne-priemgetal met meer dan honderd miljoen cijfers. Het vinden van een Mersenne-priemgetal met een miljard decimalen kan zelfs rekenen op een prijzenpot van 250.000 dollar, aansporing genoeg voor het GIMPS-project om de deelnemende computers bezig te houden.

Reacties (115)

[baasandre]

Had er nog nooit van gehoord
Dus maar eens gegezocht:

Quote" Mersenne-getallen zijn getallen van de vorm Mn = 2n-1; het is een type getallen waarvan relatief gemakkelijk kan worden vastgesteld of ze priem zijn. De grote priemgetallen die de laatste jaren werden gevonden, zijn dan ook allemaal van deze vorm. Onlangs nog (17 november 2003) werd een Mersenne-priemgetal gevonden: 220.996.011-1. Als je dat getal helemaal uitschrijft, heb je daarvoor 6.320.430 cijfers nodig. Een getal van 40.000 cijfers past nog net op één krantenpagina; voor dit priemgetal heb je dus bijna 160 krantenpagina's nodig.

Het zoeken naar Mersenne-priemgetallen gebeurt tegenwoordig via Internet. In het kader van het GIMPS-project wordt van ruim 211.000 computers de ongebruikte rekencapaciteit ingezet voor via Internet gedistribueerde berekeningen. GIMPS is zeer succesvol, de zes grootst bekende Mersenne-priemgetallen zijn alle van GIMPS afkomstig, hieronder zijn tevens de vijf grootste ooit gevonden priemgetallen. "


Dus stel je pc beschikbaar voor rekenkracht, en andere strijken daar dan geld voor op.

Goede zet, ach het zal wel ergens toe leiden.....

[Verwijderd]

Een deel van het geld (1/4e in dit geval) gaat naar het goede doel, dus dat scheelt je weer een collectebus

En is de vorm niet 2ⁿ-1? Waarschijnlijk heb je dezelfde kopieërfout als Tweakers

[baasandre]

Ja klopt...als een bus. Had het niet aangepast... beetje lui...
En dat 1/4 naar een goed doel gaat, is netjes... maar is dat na alle kosten er af zijn gegaan ?? Of ervoor......maar goed, staat wel netjes.

[Verwijderd]

...een beloning van honderdduizend dollar, uitgereikt door de Electronic Frontier Foundation. Het geld zal gaan naar de wiskunde-faculteit van de UCLA, dat 50.000 dollar krijgt, terwijl 25.000 naar liefdadigheid gaat en het resterende bedrag benut zal worden om verder onderzoek te bekostigen en om deelnemers aan de zoektocht te belonen.

1/4e van de totale beloning dus.

[kidde]

GIMPS is zeer succesvol, de zes grootst bekende Mersenne-priemgetallen zijn alle van GIMPS afkomstig

Vroegâh.

GIMPS has found 13 of the 47 Mersenne primes ever found during its 13 year history.

, rechtstreeks van de GIMPS-site gekopiëerd.

Dus stel je pc beschikbaar voor rekenkracht, en andere strijken daar dan geld voor op.

Tja, zo werkt de gemiddelde loterij ook: Jij stelt iets beschikbaar (Geld!) en meestal een ander wint de pot. Dat is echter een prima model, kijk maar hoeveel mensen meespelen.

[Verwijderd]

Dat priemgetallen handig zijn bij encryptie snap ik nog wel, maar met een cijfer van 12 miljoen getallen wordt het er niet echt handiger op. Misschien voor super geheime zaken dan?

[PiepPiep]

Juist niet helaas, bij dit getal dan.
Encryptie die grote priemgetallen gebruiken gaan er vanuit dat priemgetal*priemgetal niet makkelijk te ontbinden is in de 2 losse priemgetallen.
Als je dus een public key ziet van 22 miljoen getallen lang (in decimale getallen) dan weet je gelijk al dat het dit nieuw gevonden priemgetal is met de vorige van 10 miljoen cijfers. Andere priemgetallen van deze lengte kennen we namelijk nog niet.
Als je een public key ziet van 2000 getallen lang kan je ervanuit gaan dat het 2 priemgetallen zijn van 1000 getallen die met elkaar vermenigvuldigd zijn. Omdat een priemgetal van 1000 cijfers lang zo gevonden is en er dus ook heel veel van te vinden zijn moet je die allemaal gaan controleren of ze een factor van het 2000 cijfers lange getal zijn. Hier heb je met de huidige wiskunde vele malen meer tijd voor nodig dan het universum bestaat.

[Goderic]

Maar dat is dus alléén als je de 2 grootste priemgetallen zou gebruiken, in alle andere gevallen kun je dus wel dit priemgetal gebruiken.

Als je een public key ziet van 2000 getallen lang kan je ervanuit gaan dat het 2 priemgetallen zijn van 1000 getallen die met elkaar vermenigvuldigd zijn

Wat dacht je dan van 3 x een priemgetal van 2000 cijfers?

[.oisyn]

Wat dacht je dan van 3 x een priemgetal van 2000 cijfers?

Dat werkt niet, aangezien het algoritme een product van 2 priemgetallen nodig heeft.

[Goderic]

En sinds wanneer is 3 geen priemgetal?

[.oisyn]

Oh, ik begreep je reactie verkeerd. Ik dacht dat jij het had over het product van 3 priemgetallen. Maar je bedoelde dat een van de twee priemgetallen 3 was.

[Reactie gewijzigd door .oisyn op 27 juli 2024 09:25]

[acemoo]

Niet alle priem getallen zijn ook Mersenne priem getallen.
er zijn nog geen 50 mersenne priem getallen bekend.
terwij er miljoenen priem getallen bekend zijn.

[YopY]

...Maar als d'r maar twee Mersenne-priemgetallen in die hogere regionen zijn, dan heeft het toch geen nut? Want de 'hackers' kunnen die zo van internet halen.

[Verwijderd]

Ik zit met hetzelfde als ' terje7601':

Want als je een getal moet ontbinden in priemfactoren, overloop je eerst een lijst met alle gekende Mersenne priemgetallen (en er zijn vast nog wel lijsten met andere soorten grote priemgetallen terug te vinden die je kan gebruiken) & met wat geluk is de ontbinding zo gedaan.

Blijkbaar niet, maar waarom niet?

[.oisyn]

Klopt als een bus hoor. Voor cryptografie gebruikt niemand dan ook deze priemgetallen. Is ook wat onpraktisch, met een key van om en nabij de 10 MB. Een redelijk sterke key is momenteel bijv. 1024 bits. Dan hebben je priemgetallen de orde van grootte van ongeveer 2⁵¹² (een getal van ongeveer 154 cijfers)

[Reactie gewijzigd door .oisyn op 27 juli 2024 09:25]

[soccerroos]

waarom staat het priemgetal niet in het bericht
konden we het natellen

[.oisyn]

waarom staat het priemgetal niet in het bericht

Nou, vrij simpel. Het is 11111.....11111₂ (43.112.609 enen)

@hieronder: en misschien moet jij je kennis over het binaire talstelsel eens bijspijkeren. Net als dat 10ⁿ-1 altijd uit n negens bestaat, bestaat 2ⁿ-1 in het binaire talstelsel altijd uit n enen.

[Reactie gewijzigd door .oisyn op 27 juli 2024 09:25]

[Verwijderd]

Leuk dat je dat nog even vermeldt. Dit laat namelijk ook gelijk zien waarom de macht zelf altijd ook een priemgetal moet zijn.

Stel namelijk dat de macht niet priem is, dan zou je het altijd op een manier vergelijkbaar met het volgende kunnen ontbinden:

stel, we hebben 2^12 - 1, dan kunnen we dankzij het feit dat 12 gelijk is aan 3 * 4 schrijven als het volgende product:


100100100100 * 111

[Reactie gewijzigd door Verwijderd op 27 juli 2024 09:25]

[.oisyn]

1001001001 * 111
Voor degenen die het verband niet zien, als de p in m=2^p-1 te schrijven is als a*b, dan zal m te schrijven zijn als i*j met als i het bitpatroon bestaande uit a enen met (b-1) nullen ertussen, en met j als het bitpatroon bestaande uit b enen

Dus met bovenstaand voorbeeld, a=4 en b=3, dus
i = 1001001001 (4 enen met steeds 3-1=2 nullen ertussen)
j = 111 (3 enen)

Of: a=3 en b=4, dus
i = 100010001
j = 1111

[TrailBlazer]

De pagina zou dan 12 Megabyte worden.

[YopY]

Da's alleen als je rekent in bytes / karakter, maar aangezien het slechts 10 mogelijke getallen per karakter zijn kun je het sowieso al comprimeren naar 12*1024 megabit, een factor 12 kleiner. En dan kun je de vertaalslag naar binair nog doen, da's nog minder, maar ik kan zo niet uitrekenen hoeveel bits je daarvoor nodig zou hebben.

[Verwijderd]

Het ging hier om weergeven van het getal op deze webpagina... Het getal 123 heeft hier ook drie byte nodig. Je hebt hier dus wel de 12 Megabyte nodig.

[Verwijderd]

dus?

[Verwijderd]

Iets minder, 1mb=1024kb=1024*1024b

EDIT: @hieronder: Oke, ik had alleen maar de '12 miljoen cijfers' gelezen. Niet dat het er eigenlijk bijna 13 miljoen zijn.

[Reactie gewijzigd door Verwijderd op 27 juli 2024 09:25]

[.oisyn]

Grapjas. Aangezien het getal uit 12.978.189 cijfers bestaat, meer dan 12 MB (~12,377 MB). Bovendien comprimeert het nogal goed, aangezien je maar 10 van de 256 characters uit een byte nodig hebt.

[Reactie gewijzigd door .oisyn op 27 juli 2024 09:25]

[buzzin]

shhh....dat staat het wel, alleen stond het fout opgemaakt: 2^43,112,609-1

[Reactie gewijzigd door buzzin op 27 juli 2024 09:25]

[kidde]

Meestal komt er een poster uit. De vorige poster was geloof ik 12 meter breed, dus ik hoop dat je een grote kamer hebt. Goedkoop is de poster helaas niet.

Downloaden van het getal kan hier (Let op: 7.13Mb gezipt).

[Timv37]

En dit heeft als nut?

[JortK]

Dit heeft vooral nut voor het ontwikkelen van encryptie vormen etc.

[SMGGM]

Heb ooit iets moeten schrijven over priemgetallen. Dit komt dus rechtstreeks uit die paper (kan misschien wat saai zijn, maar is duidelijk ):
De truc van de priemgetallen wordt toegepast in de zogenaamde asymmetrische cryptografie. Hierbij is er niet één sleutel, maar zijn er twee. Een publieke sleutel en een geheime sleutel. De publieke sleutel kan door iedereen gebruikt worden om een bericht te coderen, maar alleen de ontvanger, die de publieke sleutel bekend heeft gemaakt, kan deze gecodeerde berichten ontcijferen. Het is als een hangslot. Iedereen kan het dichtklikken, maar alleen degene met de sleutel kan het weer openen. Een uitleg met een voorbeeld maakt dit duidelijk. In dit voorbeeld worden kleine priemgetallen gebruikt, maar voor echte codering worden priemgetallen van honderden cijfers gebruikt. Priemgetallen hebben een speciale eigenschap: Euclides bewees in zijn boek ’De Elementen’ dat elk natuurlijk getal (1,2,3,4 ...) op juist één manier kan ontbonden worden in priemfactoren. Met andere woorden, elk natuurlijk getal kan gemaakt worden door bepaalde priemgetallen te vermenigvuldigen. Dit kan maar op één manier. Zo bestaat 42 uit 2 x 3 x 7. Er is geen andere combinatie van priemgetallen denkbaar om 42 te vormen. En dit is precies het magische hangslot voor coderingen. Er is een wiskundige methode waarbij voor het coderen het natuurlijke getal (bijvoorbeeld 42) nodig is, maar voor het ontcijferen de unieke priemgetallen (2, 3 en 7) waaruit dit natuurlijke getal bestaat nodig zijn. Dus 42 klikt het slot dicht en 2,3 en 7 maken het open.
Het “dichtklikken” is vrij makkelijk. Neem twee priemgetallen, bijvoorbeeld 19 en 29. De publieke sleutel is nu 551, want 19 x 29 is 551. Iedereen kan nu met deze publieke sleutel een bericht coderen. Maar om dit bericht vervolgens te ontcijferen zijn 19 en 29 nodig. En die weet alleen de maker. Dit is een goede beveiliging, want twee grote priemgetallen zijn vrij makkelijk te vermenigvuldigen, maar om een groot getal te ontbinden in priemgetallen is heel moeilijk. Daarvoor voldoen op dit moment de beste computers niet eens. De boodschap is dus volstrekt veilig zolang de twee priemgetallen maar groot genoeg gekozen worden.
http://www.kennislink.nl/...getallen-in-geheimschrift

De les uit dit lang verhaal: hoe groter ze een priemgetal kunnen vinden hoe sterker de encryptie wordt. De huidige computer kan de encryptie nu nog niet gemakkelijk breken, maar de computer van over 10 jaar misschien wel. Een hoger priemgetal zorgt dus voor een sterkere codering.
Onzinnig zou ik dit dus niet noemen

[Reactie gewijzigd door SMGGM op 27 juli 2024 09:25]

[Coju]

Factorisering is een np-probleem, over 10 jaar dus nog steeds een moeilijk probleem voor computers.

[.oisyn]

Maar niet voor quantum computers mbv Shor's algoritme, die maar O(n³) nodig heeft voor een getal met n bits (of in termen van de grootte van het getal m zelf: O(log³ m)). Nou weet ik niet of quantum computers over 10 jaar hun opmars al maken (met voldoende qubits), maar het zal zeker deze eeuw gebeuren, en er is hier op t.net ook al berichtgeving geweest over quantum processors met een paar qubits.

@Faust: volgens jou niet terwijl je het zelf ook niet weet, of omdat jij er wel iets over weet en je ziet dat ik iets verkeerds zeg? Indien dat laatste zou het wel fijn zijn als je dan ook even aangeeft wat er dan niet klopt. Indien het eerste dan is het natuurlijk gewoon een loze opmerking waar niemand wat mee kan . In any way, argumentatie zou wel fijn zijn.

[Reactie gewijzigd door .oisyn op 27 juli 2024 09:25]

[Minotic]

Voor liefhebbers van quantum computers een link naar een artikel uit de scientific american.

http://www.cs.virginia.ed..._of_Quantum_Computers.pdf

In samenvatting, ze kunnen niet alles snel, maar ze kunnen wel snel dit probleem mbv Shor's algoritme oplossen.

[tofus]

Los van het feit dat deze award en het GIMPS project zelf niks met encryptie te maken hebben (zie mijn andere posts voor meer info), heeft .oisyn weldegelijk een punt.

Quantum computers zullen het einde van de veiligheid van public-key encryptie betekenen. Net zoals de rekenkracht van huidige computers het einde van de veiligheid van DES betekende.

Wat .oisyn volgens mij over het hoofd ziet, is dat op het moment dat we quantum computers kunnen gebruiken voor ontsleuteling (decryptie), er natuurlijk geen enkele reden is om niet ook quantum computers te gebruiken voor VERsleuteling (encryptie).

Shor's algoritme werkt niet bij het ontbinden van quantum-encryptie. Problem solved.

[Reactie gewijzigd door tofus op 27 juli 2024 09:25]

[.oisyn]

Wat .oisyn volgens mij over het hoofd ziet...

Nee hoor . Overigens is voor quantum encryptie geen quantum computer nodig, maar een "quantum communicatiekanaal", wat weer een heel ander ongerelateerd probleem is.

[Reactie gewijzigd door .oisyn op 27 juli 2024 09:25]

[Verwijderd]

Dat iets in NP zit, zegt helemaal niets. Een rij getallen omdraaien zit ook in NP, maar goed laat mensen je maar lekker hoog waarderen voor een zeer slordige opmerking.

[satoer]

Mooie uitleg. Ik begrijp nu dat je een publieke sleutel en geheime sleutel kan creeëren. Wat mij echter niet duidelijk is, is waarom de geencodeerde berichten niet gewoonweg weer met de publieke sleutel gedecodeerd kan worden. Die is immers bekend. Als ik iets encodeer met het bekende getal 551, waarom kan ik dit dan alleen decoderen met 19 en 29?

[tofus]

hoe groter ze een priemgetal kunnen vinden hoe sterker de encryptie wordt

@SMGGM: Mersenne primes zijn onbruikbaar in cryptografie omdat ze voldoen aan de simpele vorm 2^n-1. Brute-forcen van een op Mersenne-primes gebasseerde encryptie is dus ontzettend makkelijk, omdat je weet aan welke regel de sleutels voldoen en dus slechts een (relatief) zeer beperkte keyspace hoeft te doorzoeken.

Dit onderzoek heeft dan ook weinig tot geen impact voor de sterkte van encryptie.

Ook je beschrijving van de werking van public/private keys is niet helemaal zuiver. Zoals satoer hierboven al aangaf, leg je niet uit hoe de encryptie werkt, maar beschrijf je slechts wat priemfactoren zijn. Niet elke priemfactor is natuurlijk een public key. Zie http://en.wikipedia.org/wiki/Public-key_cryptography en http://en.wikipedia.org/wiki/RSA voor meer info.

RSA encryptie werkt inderdaad met grote priemgetallen, maar dat wil andersom nog niet zeggen dat alle grote priemgetallen altijd werken met RSA encryptie! ;p

[Reactie gewijzigd door tofus op 27 juli 2024 09:25]

[Verwijderd]

Priemgetallen worden allang gebruikt voor encryptie. En hoe groter je sleutel (priemgetallen), hoe lastiger het te kraken is.
Dus onzinnig is het niet, wel 'onhandig groot'.

[Ties86]

Het klopt inderdaad dat priemgetallen worden gebruikt voor encryptie. Dit is o.a. in gebruik bij internetbankieren ed.

Vooral voor assymetrische cryptografie worden priemgetallen gebruikt. Dit is cryptografie waarbij er twee sleutels zijn, 1 bij de zender (in de random reader) en 1 bij de ontvanger (De bank). Elke natuurlijk getal kan dan weer gemaakt worden door de afzonderlijke priemgetallen te vermenigvuldigen. Hoe groter die priemgetallen, hoe groter de sleutels dus gemaakt kunnen worden. Tot nu toe is een priemgetal van deze grootte alleen nog niet nuttig, want de huidige lengte van sleutels geeft voldoende bescherming tegen brute-force aanvallen.

Ik moest hier ook even denken aan het Sierpinski probleem, ook een DC project waar ik ooit aan heb mee gewerkt

[elnaeth]

Seventeen or Bust, bedoelde je?

[YopY]

Ik betwijfel dat getallen van 12 miljoen cijfers in programma's gebruikt worden, maar waarschijnlijk snap ik het maar half.

[i7x]

De technologie gaat snel vooruit en daarom blijft men bij met dit soort projecten. Het vinden van dit getal zal over enkele jaren geen enkele moeite meer kosten.

[Rob Coops]

Denk je? Ik denk toch echt dat er weinig echt verschl zal zijn, uit eindelijk moet je nog steeds eerst alle priemgetallen vinden en vervolgens de geen die een macht van twee -1 zijn er tussen uit vissen. Door de enorme grote van deze getallen is het rekenen er mee nog maar wat lastig over een paar jaar zullen deze getallen alleen maar groter en groter zijn en het rekenen er mee dus alleen maar lastiger.
Natuurlijk gaat de techniek vooruit en zullen we vast sneller dit getal met 12 miljoen cijfers vinden maar een getal met 100 miljoen cijfers of zelfs 1 miljard cijfers zal ook dan nog heel erg veel tijd in beslag nemen.

Uit eindelijk zal het waarschijnlijk altijd zo zijn dat het relatief makkelijk is om de getallen te vinden 12 miljoen cijfers zal een paar jaar duren en het vervolgens uitermate moeilijk zijn om deze ook in aller daagse berekeningen te gebruiken, een machine die kan rekenen met getallen van 12 miljoen cijfers zal voorlopig alleen maar een super computer zijn, en ook die zullen het er niet makkelijk mee hebben. Tegen de tijd dat een beetje PC een getal van 12 miljoen cijfers even optelt bij een ander getal van 10 miljoen cijfers zullen de gevonden getallen makkelijk uit miljarden cijfers bestaan.

[TheMazzter]

Het is niet zo dat eerst alle priemgetallen gezocht worden en dat daarna pas bekeken wordt of de priemgetallen ook Mersenne-priemgetallen zijn. Het is namelijk zo dat een getal dat te schrijven is als 2^n-1 relatief vaak een (Mersenne-)priemgetal is, als je een groot priemgetal wilt vinden is het dus handig een getal van de vorm 2^n-1 te nemen en te kijken of het een priemgetal is.

[Verwijderd]

Dat is zeker niet de voornaamste reden dat de grootste priemgetallen vaak mersenne getallen zijn. De reden hiervoor is dat er voor meresenne getallen een specifieke priemtest bestaat die veel sneller is dan de generiekere priemtesten (de lucas lehmer test).

[penetreerbeer]

Dat is nu ook grappig:

Deze getallen zullen in de toekomst zonder veel moeite kunnen gevonden worden.
en
Deze getallen zullen in de toekomst gebruikt worden voor cryptografie.

Waarom worden die getallen dan nu al gezocht als ze toch nog niet gebruikt worden en er verschrikkelijk veel rekenkracht nodig is om ze te vinden?

[siepeltjuh]

Lijk me wel logisch toch, als je pas begint met rekenen als je het nodig hebt ben je te laat. Het duurt maanden/jaren voordat je zo`n getal gevonden hebt.

http://en.wikipedia.org/wiki/Mersenne_prime

Daar kun je een mooi lijstje vinden van wanneer welke priemgetallen gevonden zijn. Nou dat is er misschien 1 per jaar gemiddeld.

*) bijna allemaal door GIMPS overigens

[Reactie gewijzigd door siepeltjuh op 27 juli 2024 09:25]

[GamingZeUs]

Omdat beide relatief aan nu zijn. Het is een race tussen ontsleutelen en versleutelen. En nu is maar weer te merken dat de versleutel kant voor ligt.

[appel437]

Voor het vinden van 243.112.609 -1 ontving het GIMPS-project een beloning van honderdduizend dollar, uitgereikt door de Electronic Frontier Foundation. Het geld zal gaan naar de wiskunde-faculteit van de UCLA, dat 50.000 dollar krijgt, terwijl 25.000 naar liefdadigheid gaat en het resterende bedrag benut zal worden om verder onderzoek te bekostigen en om deelnemers aan de zoektocht te belonen.

De EFF looft een beloning uit van 150.000 dollar voor het vinden van een Mersenne-priemgetal met meer dan honderd miljoen cijfers. Het vinden van een Mersenne-priemgetal met een miljard decimalen kan zelfs rekenen op een prijzenpot van 250.000 dollar, aansporing genoeg voor het GIMPS-project om de deelnemende computers bezig te houden.

zou jij dan geen 250.000 euro willen?

[mad_max234]

Ik betwijfel dat getallen van 12 miljoen cijfers in programma's gebruikt worden, maar waarschijnlijk snap ik het maar half.

Heb je supercomputer nodig voor de versleuteling. Nee dat lijkt me inderdaad komende jaren niet bruikbaar voor encryptie. Moet de encryptie chips toch wel met factor van 1000? toenemen de komende jaren voordat een bank dit kan laten verwerken door hun systeem .

[Reactie gewijzigd door mad_max234 op 27 juli 2024 09:25]

[blorf]

Waarom zou je een priemgetal als sleutel gebruiken? Volgens mij is dat in de verte een beetje vergelijkbaar met het gebruiken van de naam van je hond als wachtwoord. Het is een bestaand gegeven waarvan de eigenschappen bekend zijn.

[webkiller71]

Bedenk wel dat als je twee priemgetallen vermenigvuldigt, je ook een aardig goed getal hebt, maar dat dat getal vinden niet zo eenvoudig is. Verder meende ik dat er bijvoorbeeld RSA best sterk steunt op die eigenschappen.

[Jeanpaul145]

Er bestaat niet zoiets als onzinnige wetenschap. Mensen zijn nieuwsgierige wezens en dat is de grootste drijfveer voor wetenschap. Dat Hiernaast weet je niet altijd van te voren of iets in de praktijk nuttig is of niet. Denk maar aan iets alledaags als pc's.
Toen Alan Turing bezig was met het model dat inmiddels bekend staat als het Turing Machine model (accurater de Church-Turing-thesis eigenlijk) bijvoorbeeld, konden we ook niet weten dat dit van groot belang zou zijn bij het ontwikkelen van computers, en eventueel onze hedendaagse pc's.

[Yggdrasil]

Een systeem kan, ook als je het zelf bedacht hebt, zo'n complexe eigenschappen en gedragingen kennen dat je die niet zomaar kunt doorgronden.

[Verwijderd]

Inderdaad, denk maar aan de Clifford-algebra, daar wordt nog uitgebreid onderzoek naar gedaan en is als ik mij niet vergis nog niet zo veel over bekend.

[HerrPino]

Je haalt hier denk ik 2 dingen door elkaar de werkelijke wiskunde en de notatie die wij gekozen hebben. Ook voor aliens met 12 vingers en dus waarschijnlijk een twaalftallig stelsel, is dit getal een priemgetal... het wordt enkel anders genoteerd. Dus hoe je het ook noteert een priemgetal blijft in ieder notatie een priemgetal.

[bamboe]

Ja dat zou je ook denken voor encryptie vormen,
maar als ze dat getal nu bekend maken, (243.112.609 -1)
verliest het dan zijn nut niet voor encryptie technieken?

[Reactie gewijzigd door bamboe op 27 juli 2024 09:25]

[PV85]

Ik weet niet of het in de encryptie precies zo werkt.
Maar als jouw redenatie klopt zou je ook kunnen redeneren dat je met dat priemgetal niet meer moet rekenen, wat opzich ook weer nuttig is om te weten.

[My-life]

Het getal zal niet de sleutel zijn. Dan zou het idd behoorlijk stom zijn om het bekent te maken .

[Goderic]

Wat ik er van weer is dat bij encryptie 2 zeer grote priemgetallen met elkaar worden vermenigvuldigd en om de encryptie te kraken te weten moet komen welke 2 priemgetallen dat nu waren. (correct me if I'm wrong)

Dat de priemgetallen gebruikt bij de encryptie gekende priemgetallen zijn is niet erg, het duurt toch een eeuwigheid om te berekenen welke 2 priemgetallen je nu gebruikt hebt.

[Verwijderd]

Dus voor het encrypten van een bericht van 1KB zou het het beste zijn om een met een priemgetal te werken van +/- 10MB ? .... lijkt mij een beetje overdreven eerlijk gezegd..

[soepah]

Als die informatie in het bericht van 1KB zoveel waard is (voor jou of een eventuele "dief") dan kan bv een priemgetal van 10 MB (is wel zwaar overdreven) noodzakelijk zijn voor jou.
een ander vind het misschien overdreven, omdat hij de informatie van het bericht niet intressant vind.
Beveiliging (en encryptie) is vaak afhankelijk van de inhoud(informatie / waarde), niet de grootte van de informatie.

[_Thanatos_]

Het gaat over een getal van 2^43.112.609. Voor 2^64 heb je 64 bits nodig, dus voor het gevonden priemgetal (met integere precisie natuurlijk) een dikke 43Mb. Komt er dus op neer dat de opslag van zo'n getal geen 10, maar ongeveer 5,4MB opeist. Maar de breedte van integere getallen verdubbelt alleen maar, dus zul je op 64Mb uitkomen.

Maar welke computer kan nou met 64Mb-getallen werken?
128 bits is al problematisch genoeg

[Reactie gewijzigd door _Thanatos_ op 27 juli 2024 09:25]

[HerrPino]

Maar welke computer kan nou met 64Mb-getallen werken?

Het is vrij eenvoudig om met 64Mb getallen te werken, dezelfde regels die gelden voor 16,32,64 en 128 bit getallen gelden ook voor 64Mb getallen. Je kan ze alleen niet in een register proppen en zal de algoritmes zelf uit moeten schrijven. Kan me herinneren dat ik dat ook nog wel eens gedaan heb een jaar of 15 geleden.... gewoon voor de leuk, en omdat het kon

[Reactie gewijzigd door HerrPino op 27 juli 2024 09:25]

[kidde]

Dit gaat om veel meer dan wiskunde; het resultaat is slechts bijzaak.

1) Dit was het eerste 'proof of concept' van dat het gedistribueerd oplossen van problemen met 'gratis' computertijd mogelijk is. SETI en Folding@home, Rosetta etc. (die onder andere zoeken naar behandelingen tegen kanker) zijn slechts mogelijk door het pionierswerk dat GIMPS verrichte. Vele ondersoeksfaculteiten maken nu gebruik van het gedistribueerd oplossen van problemen.

2) Dit was het eerste bewijs dat voor het oplossen van problemen die enorm veel berekeningen vergen niet per sé een dure supercomputer vereist is. Het GIMPS-netwerk als totaal (45TFLOPS/s) is veel sneller dan de meeste supercomputers (hij zou nu ongeveer op plaats 90 komen). Het heeft aangetoond dat 'crowdsourcen' van problemen werkt.

3) Dit leverde - waarschijnlijk - het meest geoptimaliseerde computerprogramma ter wereld op. Het belangrijkste deel van het programma is geschreven in ASM, dat met de hand is geoptimaliseerd voor Intel processors (vandaar dat het op AMD's ook vaak 1,5x zo traag is).

Bovenstaande 3 punten zijn in mijn ogen vele malen belangrijker dan de veertien getalletjes die ze gevonden hebben.

[Proxy]

Jij hebt geen auto? Want wat heeft een auto voor nut als je ook kunt fietsen.

[Peedy]

Een steuntje in de rug voor de verbetering van cryptografie.

[tofus]

En dit [onderzoek] heeft als nut?

Het heeft als nut de grensen van distributed supercomputing te verleggen. Daar hebben ze ook de award voor gekregen.

Ook is er een wiskundig nut, zoals o.a. het bewijzen van de Lenstra–Pomerance–Wagstaff conjecture: http://en.wikipedia.org/wiki/Mersenne_prime

De toepassing in cryptografie is, in tegenstelling tot wat andere reacties in deze thread doen vermoeden, nihil. In cryptografie word doorgaans gewerkt met 1024 (hooguit 4096) bits sleutels, niet omdat ze geen grotere priemgetallen kunnen vinden, maar omdat het RANDOM priemgetallen moeten zijn (en dus geen Mersenne primes), en het genereren van een zuiver random priemgetal is gewoon te kostbaar (qua CPU cycles, maar ook qua beschikbare entropie) als dat voor meer bits zou moeten. Ook worden de toegepaste algoritmes te traag voor dagelijks gebruik (real-time telecommunicatie/PIN automaten, etc.) bij grotere bit sleutels.

Het 'nut' van dit onderzoek is dus puur wetenschappelijk. Het leidt tot betere, snellere supercomputers en een beter inzicht in de nummer-theorie achter Mersenne priemgetallen.

[Reactie gewijzigd door tofus op 27 juli 2024 09:25]

[Robbaman]

Ik vraag me soms wel eens af waar het nieuws op deze site vandaan komt. Volgens Wiki (niet de meest betrouwbare bron, ik weet het) zou dit getal al op 12 april zijn ontdekt. (of het moet natuurlijk om een ander getal gaan. Die op wikipedia genoemd wordt heeft 12837064 getallen)

Is er recent iets gebeurd waardoor dit weer actueel is?

[Reactie gewijzigd door Robbaman op 27 juli 2024 09:25]

[Munters]

Het is heel simpel: ze hebben een heel groot mersenne priemgetal ontdekt, maar niet het grootste tot nu toe. Vorig jaar september is er eentje ontdekt die nog eens grofweg 140.000 cijfers meer heeft.

[Verwijderd]

Is het niet logischer om gewoon alle getallen in volgorde af te gaan? Hoe ontdekken ze eerst een groot en dan een kleiner (ofja, klein...) getal?

[kidde]

Is het niet logischer om gewoon alle getallen in volgorde af te gaan?

Nee, en wel om de volgende reden:

Uitzoeken of een 'normaal' getal van 12 miljoen cijfers een priem is, duurt meestal heel lang, als je het niet door kleine getallen kan delen. Misschien 3000 jaar op een gemiddelde Tweakers-CPU.

Voor Mersenne-getallen is er echter een veel sneller algoritme dat ervoor zorgt dat je hetzelfde kan uitvinden in 3 maanden. Het gaat hier om de Lucas-Lehmer test. Dat algoritme werkt echter alleen voor getallen geschreven in de vorm 2^n-1. Dus voor getallen die in die vorm zijn geschreven zijn kan je 10.000 maal sneller uitvinden of het priemgetallen zijn of niet. Dan is het dus logisch dat je die getallen gaat onderzoeken.

Ed: Dus wat men doet: Men gaat inderdaad alle priemgetallen af op volgorde, maar dan neemt men twee tot de macht dat getal en dan min een. Dus men gaat voor 'n' in '2^n-1' alle getallen op volgorde af.

[Reactie gewijzigd door kidde op 27 juli 2024 09:25]

[.oisyn]

Het (tot nu toe) 46e mersenne-priem is ontdekt ná de 47e waar dit artikel over gaat. Bovendien weten ze vanaf de 40e priem niet zeker of er idd priemen tussen zitten. Ze gaan dus niet letterlijk de priemen in volgorde af, om de redenen die ik in de reactie hierboven heb uiteengezet.

[.oisyn]

Het is een gedistribueerd project, waardoor iedereen een eigen stukje workload krijgt om aan te werken. Een simpel voorbeeld: stel er zijn 10 mensen, en je wilt alle getallen weten die deelbaar zijn door 3. Dan geef je al die tien mensen een getal tussen de 1 en de 10, en iedereen gaat dan proberen of zijn getal deelbaar is door 3, en rapporteert dat vervolgens terug. Op die manier kan de persoon die 6 had zeggen dat het deelbaar is door 3 voordat de persoon die 3 had dat zegt, bijvoorbeeld omdat ie sneller is in rekenen

[buzzin]

Als je even de link volgt, zie je dat ze 2 dagen geleden pas de prijs hebben gewonnen....dat zal wel de reden achter het nieuws item zijn denk ik dan?
Overigens duurt het bevestigen van zo'n nummer ook altijd even...

[.oisyn]

Je kijkt verkeerd. Dit getal is vorig jaar 23 augustus al ontdekt. Dit artikel gaat trouwens over het feit dat ze de prijs uitgereikt krijgen, de kop van het artikel is dus ook wat onhandig gekozen. De ontdekking zelf staat trouwens gewoon bij de relevante artikelen: nieuws: Onderzoekers ontdekken priemgetallen met meer dan tien miljoen cijfers (van september vorig jaar)

Overigens bedoel je "cijfers", niet "getallen". Een getal is samengesteld uit cijfers

[Reactie gewijzigd door .oisyn op 27 juli 2024 09:25]

[Verwijderd]

Even een vraagje... als dit zo is dan weetje toch ook dat het getal 2^(2^43112609-1)-1 ook een Mersenne-priemgetal is.... Of heb ik dit nu verkeerd.... (het enige probleem is dat je niet zeker weet welk getal dit in die reeks is)

[.oisyn]

Ja dat heb je verkeerd. Sterker nog, dat getal is per definitie geeneens een priemgetal, want 43112609-1 is geen priemgetal (namelijk deelbaar door 2). Een mersenne-getal 2^p-1 is alleen priem als p ook priem is. Overigens betekent dit weer niet dat alle mersenne getallen priem zijn waarvoor geldt dat p ook priem is (zie bijv. p=11)

.edit: oh wacht, ik heb je reactie verkeerd gelezen (ik zag de tweede 2^ niet). Echter heb ik wel het antwoord gegeven: het staat niet vast dat 2^p-1 een priemgetal is als p een priemgetal is. Bij p=11 krijg je 2047, en dat is geen priemgetal (deelbaar door 23 en 89)

[Reactie gewijzigd door .oisyn op 27 juli 2024 09:25]

[kidde]

Misschien nutting om te vermelden dat van de door GIMPS grofweg 2 miljoen geteste getallen er maar 13 Mersenne priem waren. Dus de kans is niet al te groot.

[Munters]

Dat is niet gegarandeerd. Er is grote kans dat 2^(mersenne-priem)-1 weer een mersenne-priem is.
Maar dat is dus niet zeker. Het probleem zit dus in het bewijzen, en dat is voor jouw recursieve voorbeeld nog even een brug te ver.

Andersom geldt overigens wel: Als 2^n-1 een mersenne-priem is, dat is n gegarandeerd een (gewone) priem.

[Ruben314]

243.112.609 -1 = 243112608 is geen priemgetal.
Misschien 2^243.112.609 -1 ?

[buzzin]

Ja, als je de link volgt staat het daar wel goed....het kopiëren is blijkbaar mis gegaan

Het is dus: 2^43,112,609-1

[florisje]

nee, het is 2^43.112.609 - 1

ik heb er een paar jaar geleden ook heel veel processortijd in gestoken

[Reactie gewijzigd door florisje op 27 juli 2024 09:25]

[Verwijderd]

correct 2^x - 1, dat niet het product is van 2 of meer kleinere factoren

[MadMarky]

12 miljoen cijfers, damn das groot. Stel je zou het als ASCII (platte tekst) opslaan, dat levert je al een tekstbestand van 11,4MB op. Enkel aan cijfertjes

[Munters]

Gelukkig kun je het vrij goed comprimeren. Bijvoorbeeld tot 2^43112609-1.

[Verwijderd]

Ja, maar dat is nou net het punt. Als het triviaal was om uit te rekenen hoeveel 2^43112609-1 precies is, dan is het hele nut ervan weg voor cryptografie. :-P

[Munters]

Nee hoor. Uit uitrekenen van deze twee-macht is triviaal, en (voor een computer) zeer snel te doen.
Ik zal hem even Hex voor je uitschrijven: 1FFFF....FFFFFF (10.778.152 F'jes).

Het gaat er om dat als je twee van dit soort getallen hebt, en deze onderling vermenigvuldigd tot een nog veel groter getal, je de twee priemdelers niet eenvoudig kunt vinden als je deze niet al weet.

Overigens wordt dit mersenne priemgetal echt niet praktisch ingezet voor cryptografische mogelijkheden. Iedereen moet immers twee eigen unieke priemgetallen hebben.

Dus ja, grote priemgetallen worden gebruikt in de cryptografie.
En nee, dit bewijs heeft geen praktische waarde voor de cryptografie.

[Darkwings]

Dat is triviaal

(1 << 43112609-1) ^ 1

Je moet alleen ff een type hebben waar je zulke grote getallen in op kan slaan/bewerken, maar daar zijn libs voor

[.oisyn]

Je bedoelt (1 << 43112609) - 1. En in feite zijn dat binair gezien gewoon 43112609 1'en achter elkaar.

[Darkwings]

Je hebt uiteraard gelijk

Ik wilde stoer doen met 'n xor op vrijdagmiddag

[.oisyn]

Euhm, het ís triviaal om uit te rekenen hoeveel dat is. Het probleem in cryptografie is het ontbinden in factoren van een heel groot samengesteld getal. Wat overigens wel weer een eitje is voor een quantum computer, dus tegen die tijd moeten we ook aan de quantum cryptografie

@MadMarky: het was trouwens 12,98 miljoen cijfers, dus zeg maar gerust 13

[Reactie gewijzigd door .oisyn op 27 juli 2024 09:25]

[terje7601]

Als dit nuttig is in encryptie, waarom worden de gevonden priemgetallen dan steeds bekendgemaakt? Op die manier zijn ze toch niet meer bruikbaar?
Want als je een getal moet ontbinden in priemfactoren, overloop je eerst een lijst met alle gekende Mersenne priemgetallen (en er zijn vast nog wel lijsten met andere soorten grote priemgetallen terug te vinden die je kan gebruiken) & met wat geluk is de ontbinding zo gedaan.

[corné]

Nouja, de source van bijvoorbeeld AES encryptie is ook bekend, maar dat is ook niet zomaar te decrypten.
Ik weet alleen niet of dit vergelijkbaar is