Onderzoekers ontdekken priemgetallen met meer dan tien miljoen cijfers

Onderzoekers hebben bekendgemaakt dat er twee nieuwe Mersenne-priemgetallen zijn ontdekt: 2^43.112.609-1 en 2^37.156.667-1. Beide getallen bestaan uit meer dan tien miljoen cijfers. De vinders krijgen een geldbedrag.

Een priemgetal is een natuurlijk getal groter dan 1 dat slechts deelbaar is door 1 en door zichzelf. Voor Mersenne-priemgetallen geldt de extra voorwaarde dat het getal geschreven kan worden als 2^p-1, waarbij p ook een priemgetal is. De eerste Mersenne-priemgetallen zijn 3, 7, 31, 127 en 8191. De rij met priemgetallen is oneindig en er bestaat dus geen allergrootste priemgetal, aangezien er altijd een grotere te vinden is. Het aantal bekende Mersenne-priemgetallen is derhalve nog steeds groeiende, zo laten de recente ontdekkingen zien. Priemgetallen worden onder meer gebruikt voor encryptie en het genereren van toevalsgetallen.

In 2006 was voor het laatst een Mersenne-priemgetal ontdekt, namelijk 2^32.582.657-1. Twee jaar lang was het rustig op het Mersenne-priemgetalfront, maar op 23 augustus van dit jaar werd het getal 2^43.112.609-1 aan het lijstje met bekende priemgetallen toegevoegd, een getal van maar liefst 12.978.189 cijfers. Op 6 september werd het Mersenne-priemgetal 2^37.156.667-1 ontdekt; dit getal bestaat uit 11.185.272 cijfers.

Het tot nu toe grootste Mersenne-priemgetal is ontdekt door Edson Smith, terwijl de meest recente ontdekking op naam staat van Hans Michael Elvenich. Beide heren deden mee aan het Gimps-project, waarbij computers over de hele wereld via distributed computing meerekenen aan het vinden van Mersenne-priemgetallen. Het prijzengeld wordt als volgt verdeeld: 25.000 dollar gaat naar goede doelen, 50.000 dollar naar de Universiteit van Californië in Los Angeles voor haar aandeel bij de ontdekking en de rest van het bedrag wordt verdeeld onder de overige ontdekkers die meededen aan Gimps.

Reacties (134)

[MSalters]

Fout in artikel: alhoewel er bewijsbaar geen hoogste priemgetal is, is dat niet bewezen voor Mersenne priemgetallen. Het kan dus goed dat dit het laatste Mersenne priemgetal is.

Het algemene bewijs is simpel: N! + 1 is niet deelbaar door getallen 1..N. Maar als P het hoogste priemgetal is, waar is P! + 1 dan door deelbaar? Niet door getallen 1..P. Niet door priemgetallen > P (bestaan per definitie niet). Dus P!+1 zou zelf een priemgetal zijn, hoger dan P - oftewel, zo'n P bestaat niet.

Voor Mersenne priemgetallen gaat dat bewijs niet op. Die hebben de vorm 2^p-1. Er kan een laatste Mersenne Priemgetal zijn, in welk geval alle hogere priemgetallen een andere vorm hebben.

[Anoniem: 125126]

Als er een oneindige reeks priemgetallen is, dan is the reeks 2^p-1 (met p is priem) dus ook oneindig. Maw er is dan ook een oneindige reeks Mersenne priemgetallen. Ik kan iets over het hoofd zien (wat nog wel eens gebeurd )

[Anoniem: 216532]

Da's net iets te eenvoudig bekeken. Er zijn idd oneindig veel priemgetallen p, maar lang niet elk Mersenne-getal is een priemgetallen: 46 op 43112609. Het kan best zijn dat het op een bepaald ogenblik ophoudt. We weten het gewoon (nog) niet.

[.oisyn]

De fout die je maakt is dat hoewel de reeks Mersenne getallen idd oneindig is, is niet ieder Mersennegetal een priemgetal. Dat er oneindig veel getallen zijn in de vorm 2^p-1 wil nog niet zeggen dat er ook oneindig veel getallen uit die set ook daadwerkelijk priem zijn. Vooralsnog is er nog geen bewijs gevonden dat zegt dat het aantal Mersenne priemen eindig danwel oneindig is.

[Anoniem: 216532]

Je moet het bewijs van Euclides nog eens goed bekijken. Het gaat hem niet om P!, maar om het product van alle priemgetallen kleiner of gelijk aan P.
P!+1 is lang niet altijd een priemgetal:
4!+1=25=5*5,
5!+1=121=11*11,
enz.

Bovendien is het bewijs iets langer dan je aangeeft. En bewijs je enkel dat er oneindig veel priemgetallen zijn. Heeft niks met Mersenne te maken.

Edit:
gewoon even uit nieuwsgierigheid getest hoe vaak P!+1 wel een priemgetal is, voor P <= 100. Het zijn er echt niet zoveel:
2!+1 = 3
3!+1 = 7
11!+1 = 39916801
27!+1 = 10888869450418352160768000001
37!+1 = 13763753091226345046315979581580902400000001
41!+1 = 33452526613163807108170062053440751665152000000001
72!+1 = 4470115461512684340891257138125051110076800700282905015819080092370422\
104067183317016903680000000000000001
77!+1 = 1451830920282858696340707840863082849837403792242083588467815746880619\
91349156420080065207861248000000000000000001


Maar om te testen of dit priemgetallen zijn heb je dus al speciale software nodig, zoals Mathematica.

[Reactie gewijzigd door Anoniem: 216532 op 23 juli 2024 18:46]

[.oisyn]

Je moet het bewijs van Euclides nog eens goed bekijken. Het gaat hem niet om P!, maar om het product van alle priemgetallen kleiner of gelijk aan P.
P!+1 is lang niet altijd een priemgetal:
4!+1=25=5*5,
5!+1=121=11*11,
enz.

Ik denk dat jij degene bent die er nog eens naar MSalter's bewijs moet gaan kijken. Zoals MSalters al zei, N!+1 is niet deelbaar door een getal 1..N. Vervolgens kom je met het voorbeeld 4!+1 = 25 = 5*5. N was 4, dus 5 is niet een getal uit de set 1..N. En ja, 5 is een priemgetal. Maar het gaat dus niet in tegen hetgeen MSalters beweerde, namelijk dat N!+1 niet deelbaar is door een getal kleinergelijk N. Niemand beweert hier dat N!+1 altijd een priemgetal is.

De stelling is: er bestaat een maximaal priemgetal P. Maar, P!+1 kan niet deelbaar zijn door een getal kleinergelijk P. Echter bestaan er geen priemgetallen groter dan P (dat was de stelling), dus het getal waar het wel deelbaar door is moet samengesteld zijn uit priemgetallen kleinergelijk P. Maar dat impliceert dat het ook deelbaar moet zijn door die priemgetallen, en dat is het niet. Ergo, de stelling is in tegenspraak en klopt dus niet. De enige conclusie die je hieruit kunt trekken is dat er geen grootste priemgetal bestaat.

Dat het bewijs zoals gepostuleerd door MSalters niet hetzelfde is als het bewijs van Euclides wil niet meteen zeggen dat z'n bewijs niet klopt.

[Reactie gewijzigd door .oisyn op 23 juli 2024 18:46]

[Anoniem: 231832]

Hoe wordt dat nu eigenlijk aangepakt dat berekenen/ controleren van die giga-priemen? gewoon op de ouderwetse manier door de priem P door iedere voorgaande priem V te delen ( tot en met de helft van P natuurlijk, verder hoef je niet te gaan) ??? iemand??? niemand???

Alvast bedankt.

[.oisyn]

( tot en met de helft van P natuurlijk, verder hoef je niet te gaan)

Veelgemaakte "fout". De helft is veel te ver. Je hoeft maar tot en met √P, want √P*√P=P. Dus, als er een deler N bestaat die groter is √P, dan is M=P/N kleiner dan √P en is M bovendien ook een deler. Derhalve, als je weet dat er tussen 2 en √P geen delers bevinden, dan bevinden zich er ook geen delers tussen √P en P, en hoef je dus niet verder te zoeken.

Dit natuurlijk nog even naast het feit dat ze daar veel ingewikkeldere algoritmen voor gebruiken die een stuk sneller zijn .

[Reactie gewijzigd door .oisyn op 23 juli 2024 18:46]

[Anoniem: 216532]

Inderdaad veel voorkomende fout, maar in dit geval klopt het (toevallig?) wel: E_E_F deelt immers de exponent P door 2, is dus "vierkantswortelen" :-)

[Anoniem: 231832]

Nee hoor, ik zat inderdaad fout ... het was al weer een tijdje geleden dat ik met priemen bezig ben geweest maar je hoeft inderdaad niet verder te gaan dan de wortel van de priem... goed opgemerkt .oisyn !

Alleen graag wat meer toelichting over:
"ingewikkeldere algoritmen voor gebruiken die een stuk sneller zijn ."

[Reactie gewijzigd door Anoniem: 231832 op 23 juli 2024 18:46]

[FreezeXJ]

Daar hebben ze wat kunstjes op bedacht, Proths Theorem is de belangrijkste.
Simpelweg een serie berekeningen uitvoeren, en elke die lukt geeft je een grotere kans dat ie priem is. (100% bewijs geeft het niet, maar het komt er aardig dicht in de buurt... Een aantal sneakt er helaas tussendoor, maar so far valt het mee.

[.oisyn]

Proth primes zijn heel wat anders dan Mersenne primes. Een Proth prime heeft de vorm k∙2ⁿ+1, met k een oneven getal kleiner dan 2ⁿ. Een Mersenne prime heeft de vorm 2ⁿ-1, een wereld van verschil.

[Reactie gewijzigd door .oisyn op 23 juli 2024 18:46]

[Anoniem: 231832]

Dat was oorspronkelijk dan ook niet mijn vraag.

[.oisyn]

Je vraag was hoe dit soort grote priemkandidaten getest worden of ze daadwerkelijk priem zijn. Aan Proths theorem heb je alleen wat als je weet dat de kandidaat een Proth getal is, oftewel geschreven kan worden als k∙2ⁿ + 1, met k oneven. Hier gaat het om het vinden van Mersenne priemgetallen, die geschreven worden als 2ⁿ-1 met n een priemgetal. Voor het testen van een Mersenne priem heb je dus compleet niets aan Proths theorem. Het werkt dan ook andersom: Mersenne en Proth getallen zijn kandidaten voor priemgetallen, waarbij je bij Proth getallen Proths theorem kunt gebruiken om te testen of ze daadwerkelijk priem zijn. Voor Mersenne getallen heb je andere tests nodig, met name de Special number field sieve

[Reactie gewijzigd door .oisyn op 23 juli 2024 18:46]

[kuifware26]

Je kunt controleren of hij priem is met de Lucas-Lehmer test (zie http://www.mersenne.org/math.htm, kopje 'Lucas-Lehmer testing'). Uiteraard zet je daarvoor een computer aan het werk; het duurt op een gewone computer al snel een maand voor deze grote getallen.

[increddibelly]

w00t??

Voor Mersenne-priemgetallen geldt de extra voorwaarde dat het getal geschreven kan worden als 2p-1, waarbij p ook een Mersenne-priemgetal is.

Smith krijgt als vinder van het eerste Mersenne-priemgetal van meer dan tien miljoen
cijfers een bedrag van 100.000 dollar. Elvenich moet het doen met 50.000 dollar.

dus in feite verdient hij enkele modale jaarsalarissen door een formule in te vullen?

Dan is in mijn ogen het uitrekenen van priemgetallen een net iets minder loze dagbesteding geworden. (jaja ook al worden ze onder meer gebruikt voor encryptie en het genereren van toevalsgetallen.)

[miw]

Er zijn niet zoveel Mersenne priemgetallen bekend. Ook geldt niet voor alle priemgetallen P dat 2^P-1 ook een priemgetal is (simpelste tegenvoorbeeld is het priemgetal 11). Voor deze grote getallen moet er dus steeds uitgerekend worden of het getal wel priem is. Dat is een uiterst rekenintensief karwei.
Een onderzoeker kan dan rekentijd inkopen op een duur rekencentrum, of een community effort opstarten en een prijs uitloven voor een positief resultaat. Volgens mij is een onderzoeker dan goedkoper uit.

[Munters]

Het invullen van de formule is niet zo moeilijk nee.
Ik zal het even doen: 2^(2^43.112.609-1)-1, zo, dat lijkt me een prima kandidaat.
Nu nog even bewijzen dat het echt een priemgetal is. Dat is natuurlijk de uitdaging.

[Bits!]

En daar wordt dus die shared rekenkracht voor gebruikt.

[kidde]

Nee, niet exact. Om dat te bewijzen heb je geen shared rekenkracht nodig, want dat bewijzen kost niet eens zoveel rekenkracht. Dat kan je namelijk op een moderne Intel binnen een maand doen.

De rekenkracht is nodig niet omdat de som zo moelijk is (OK, je Pentium rekent er meer dan een maand over, maar dat is relatief kort), maar omdat er zoveel werk is. Er zijn honderdduizenden getallen die gecontroleerd werden en niet priem bleken te zijn. De kans dat je per ongeluk een Mersenne-priemgetal vind door te gokken is klein; net zo klein als dat je een random wachtwoord probeert te raden. Dus de snelste manier is 'brute forcen'; gewoon alle mogelijkheden proberen.

Kijken of één wachtwoord het juiste is kost dus niet veel moeite, en dat hoef je niet te distribueren. Het testen welke van een miljoen mogelijke wachtwoorden de juiste is; daar gaat het om.

[Krylinck]

Je stelt via een gedownload programmatje je computer deels beschikbaar voor het zoeken naar die getallen. Je vult dus niks zelf in, maar je leent wel een deel van je bezit uit. Als je dan door toeval iets bruikbaars vindt, wordt dat lenen een soort huren. De meeste mensen doen eraan mee omdat ze weten dat als ze toevallig een Marsenne-getal vinden, er een beloning tegenover staat. Ik neem aan dat er anders minder mensen participeerden, op de echt geïnteresseerden na.

[wiene]

Iemand enig idee hoe lang het duurt om zo'n getal te controleren?

Moeten ze mbv een script het mersenne-priemgetal gaan delen door alle oneven getallen en dan maximaal tot op ca 1/3e van het getal? Immers als je deelt door een getal is de kleinst mogelijke uitkomst als het geen priemgetal zou zijn 3 toch? Veelvouden van getallen kun je overslaan: 3, 5, 7 als kleinste dan kun je de volgende overslaan: 9,15,21, 25, 27 etc. Wel moet dan 11, 13, 17 maar 121 dan weer niet etc.

Er zou toch een formule voor moeten zijn zou je denken. Als je namelijk mbv vermenigvuldigen gaat testen welke oneven getallen juist wel deelbaar zijn door een getal (met de p=2^n-1 regel in acht houdende) zie je vanzelf in de reeks welke overgeslagen worden. Dit zou dan een mersenne priemgetal moeten zijn. Maar dit zal wel even makkelijk denken zijn van mij waar ik iets vergeten ben. Verder is er natuurlijk enorm veel computerkracht voor nodig.

Maar als je de formule ontdekt kun je de oneindige priemgetallen zoeken in de juiste volgorde, het kan alleen een tijdje duren voordat een computer de volgende berekend heeft.

[Reactie gewijzigd door wiene op 23 juli 2024 18:46]

[kidde]

Iemand enig idee hoe lang het duurt om zo'n getal te controleren?

Het moeilijke antwoord: Hangt van je computer af.
Het makkelijke antwoord: Ga naar benchmarks pagina Mersenne, getal invullen, proc invullen, en klaar.

[wiene]

Dat snapte ik al natuurlijk maar een indicatie met een huidige computer bedoelde ik eigenlijk. Duurt wel erg lang als ik die site van je zie. Bedankt. Ik kan me dan in ieder geval wel voorstellen hoe lang het duurt voordat je een nieuw priemgetal hebt als je al een formule zou hebben.

Je zou toch zeggen dat in de reeks van mersenne priemgetallen ook een verband zit. Kennelijk niet.

[Anoniem: 231832]

Feitelijk hoef je dan niet meer te zoeken, als je die formule hebt.

Verder is een priem uit zijn voorgangers (zonder ook maar 1 over te slaan) te berekenen... maar dat kost ook heel veel rekenkracht, als je bijvoorbeeld de 10 miljoenste priem moet hebben.

Er is dus wel een formule maar die levert nog niet echt veel voordeel. Het probleem is daarmee ook dat de formule ontzettend veel andere priemen oplevert en niet noodzakelijk de volgende in de reeks.

[Reactie gewijzigd door Anoniem: 231832 op 23 juli 2024 18:46]

[Anoniem: 216532]

Het algoritme dat jij waarschijnlijk bedoelt is in de praktijk maar zinvol voor relatief kleine getallen. Mensen onderschatten heel vaak het enorme van Echt Grote Getallen. Voorbeeldje: 10^60, een getal van slechts 61 cijfers. Met het lagere-schoolalgoritme moet je dan 10^30 tests doen (da's de vierkantswortel, en niet 1/3!). Zelfs als je een miljard tests per sekonde kan doen duurt heel het verhaal zo'n 10^14 jaar, of enkele duizenden keren de levensduur van het heelal. Als je een miljard PCs parallel zou laten werken duurt het nog 32000 jaar. En da's dan nog een getalletje van ocharme 61 cijfers.

De theorie achter de gebruikte factoring methoden (Elliptic curve method, Special number field sieve, ...) is heel complex, en is onmogelijk te begrijpen zonder een diepgaande studie van getallentheorie.

Priemgetallen zijn dan wel nuttig in encryptie, maar getallen van miljoenen cijfers hebben hier echt geen meerwaarde. Het product van twee priem[edit]getallen van 100 cijfers factorizen duurt al zo lang dat het voor de meeste toepassingen als onkraakbaar beschouwd kan worden, en als je vreest voor steeds krachtigere computers neem je er een paar van 1000 cijfers, en dan zit je weer voor een tijd goed.
Tot we een echt werkende quantumcomputer hebben, maar die heeft ook met tien miljoen cijfers geen moeite...

[Reactie gewijzigd door Anoniem: 216532 op 23 juli 2024 18:46]

[gepebril]

Hele interessante discussie. Kan iemand me vertellen waarom nou juist priemgetallen zo goed zijn voor encrptie? Ik bedoel waarom is dit getal nou moeilijker te raden dan zijn broertje die de waarde 1 hoger of lager ligt??

[.oisyn]

Het is niet dat er priemgetallen worden gebruikt omdat ze moeilijk te raden zijn, maar omdat ze bepaalde eigenschappen hebben die van belang zijn voor encryptie. Verder heb je natuurlijk grote sleutels nodig om de effectiviteit van een brute force attack te verminderen, dus vandaar ook grote priemgetallen (maar niet in de orde van grootte van de priemgetallen waar dit nieuwsbericht over gaat)

[Peenutzz]

Waarom krijgen mensen geld voor het vinden van iets waarvan men weet dat het bestaat?

[Krylinck]

Omdat de getallen gebruikt kunnen worden "voor encryptie en het genereren van toevalsgetallen". Er is dus wel degelijk een nut, alleen moet je dan wel het exacte getal weten. Iedereen weet dat ze bestaan, maar pas als je er één hebt gevonden, kun je hem gebruiken. Logisch toch?

[DarkTemple]

Omdat de getallen gebruikt kunnen worden "voor encryptie en het genereren van toevalsgetallen". Er is dus wel degelijk een nut, alleen moet je dan wel het exacte getal weten. Iedereen weet dat ze bestaan, maar pas als je er één hebt gevonden, kun je hem gebruiken. Logisch toch?

Maar niet deze extreem grote getallen.

[Matis]

Priemgetallen zijn super belangrijk bij het encrypten van gegevens, denk aan SHA1. Hoe groter het priemgetal, des te moeilijker te kraken!

[BramT]

SHA (1) is een hash-algoritme en heeft niets te maken met encrypting of priemgetallen. Je bedoeld misschien het op het web gebruikte SSL (https).

^{/edit: nu nog beter: met linkje!}

[Reactie gewijzigd door BramT op 23 juli 2024 18:46]

[elmuerte]

Hash algoritmes hebben weldegelijk iets te maken met priemgetallen. De initialization vector van hash functies bestaat bijna altijd uit alleen priemgetallen.
Maar grote priemgetallen zijn niet interesant voor hash algoritmes. Maar wel voor asymmetric cryptography zoals RSA.

[guanothan]

Volgens mij is de initialization vector van MD5 simpelweg waarden uit de sin() functie. Priemgetallen hierin zouden toeval zijn en geen functie dienen.

[SKiLLa]

Laat sinus (een reeksontwikkeling 'functie') nou juist gebruikt kunnen worden om priemgetallen uit te rekenen (zie formule).

En MD5 is in dit geval een slecht voorbeeld; het is sinds allang 'gekraakt' en wordt vooral nog voor checksums gebruikt. Natuurlijk kun je MD5 combineren met salting en key strengthening, maar dan is de toegevoegde waarde van MD5 tov. de rest te verwaarlozen. In die context worden hash algo's als SHA of RIPEMD gebruikt.

[? ?]

en deze priemgetallen gaat niemand gebruiken
onze encryptie steunt op het feit dat het product van twee priemgetallen niet eenvoudig te herleiden is naar deze twee priemgetallen. zeer bekende exemplaren zou men al eens kunnen testen

[MSalters]

Het probleem is niet alleen dat deze priemgetallen bekend zijn, maar ook nog eens binair de vorm 111111....111111 hebben; er komt geen 0 in voor !

[JackBol]

Tja, das nogal logisch als je ze in de vorm van (2^x)-1 kan schrijven.

[BramT]

Muh? Hoe kom je daar nou bij?

5 = 101
11 = 1011
13 = 1101

Daarintegen is 1111 = 15, wat weer geen priemgetal is.

/edit: O, je bedoeld deze als in Mersenne priemgetallen.. ok dan

[Reactie gewijzigd door BramT op 23 juli 2024 18:46]

[DarkTemple]

correct, maar deze uitzonderlijk grote getallen kunnen niet gebruikt worden!
dat zou te lang vergen qua rekentijd

[Tsurany]

Nu nog niet, maar de rekenkracht word steeds groter en daar kan je als encryptiebedrijf niet achteraan lopen, je moet zorgen dat je daar op vooruit loopt.

[harrald]

waarom dan nu zoveel rekenkracht spenderen aan iets waar je pas wat mee kan als je meer rekenkracht hebt? eer de tijd aanbreekt dat je het kan gebruiken, zou je het dus ook veel makkelijker kunnen vinden...

iets zegt me dat ze ze wel degelijk kunnen gebruiken voor iets.

[Wh4ck0]

omdat wanneer je ze makkelijk kan berekenen, ze niet meer bruikbaar zijn.

[Sunbeam-tech]

iets zegt me dat ze ze wel degelijk kunnen gebruiken voor iets.

Misschien in de ruimtevaart of sterrenkunde?
Kan makkelijk zijn voor het berekenen van enorme afstanden met lichtjaren of iets met de uitbreiding van het heelal.
In de ruimtevaart techniek of sterrenkunde word heel vaak met belachelijk grote getallen gewerkt.

Of natuurlijk het andere uiterste, de wereld van de atomen en ander enorm klein spul

[DarkTemple]

Waarom niet wachten dan tot je meer rekenkracht hebt met het uitrekenen? Dan gaat dat nl ook een stuk sneller.

[gabiballetje]

Dan is een gemiddelde PC dus zo snel dat iedereen het kan, en heeft het dus geen zin om het te gebruiken, gezien de beveiliging dan niet moeilijk te kraken is.
Het idee is dus, dat dergelijke getallen nu gevonden worden, en gebruikt kunnen worden, nu het een bekend getal is, voor encryptie.
Krakers hebben er dan niets aan, gezien hun systeempje niet weet WELK getal gebruikt is, en hun dus, in hun eentje ipv een mega systeem, het moeten berekenen, wat dus jaren gaat duren. Derhalve is het nut van een dergelijke operatie 0,0.
Dus, voor bepaalde bedrijven heeft het wel degelijk nut, voor de gemiddelde persoon, helemaal geen, ik zou haast zeggen minder dan geen, maar dat kan niet

Net zoiets als de wapenwedloop, mocht je dat wel snappen.
De Russen bouwen een dikke bom, de Amerikanen willen er over heen blijven gaan. De Russen gaan ook weer door, ipv te denken, ach, over zoveel jaar kunnen we ineens dikkere bommen maken, dus waarom door gaan ? Omdat je dan nu dus de lul bent en niets uit kunt vreten.
Het bekijkt het van een iets andere kant maar het effect blijft hetzelfde.

[Matis]

Bedankt , je neemt de woorden uit mijn mond (figuurlijk natuurlijk)

[purper]

Deze twee getallen kan je inderdaad niet meer gebruiken, omdat ze bekend zijn...Het product is als publieke key nu eenvoudig te ontbinden in de twee priemgetallen om het geheel weer te decoderen.

[Anoniem: 118036]

Het doel van beveiliging is niet om iets onkraakbaar te maken, maar om er voor te zorgen dat het zo lang mogelijk duurt voordat het gekraakt wordt. Dat is in ieder geval de praktijk.
In het verlengde daarvan is dit een goed stap. Het betekent namelijk een vertraging van een factor 100, misschien wel meer.

[GENETX]

Men weet dat er grotere (abstract) priemgetallen zijn, niet welke getallen (exact) hier nog meer onder vallen.

[Anoniem: 253596]

Omdat het onderzoek erna om het te vinden niet iets is wat je in een dag even doet daarom staat er een bedrag achter. daarnaast encryptie en dergelijke dingen worden in veel industrien gebruikt dus die hebben er belang bij en dus stellen financile middelen beschikbaar.

[Anoniem: 62763]

omdat ze de moeite hebben genomen het te zoeken.

[kluyze]

Ik vraag me eerder af waarom die mensen geld krijgen voor iets wat ze verkregen hebben door distributed computing en dus niet zelf gezocht hebben.

Natuurlijk als je dat geld moet verdelen onder al die kleine nodes gaat er per node niet veel overblijven. Maar ze kunnen het tenminste aan een goed doel schenken.

[kidde]

Zowiezo krijgt het project een deel van het geld. Ook de afgelopen vinders van Mersenne priemgetallen die kleiner zijn dan 10M cijfers decimaal krijgen nog een deel van het geld.

Je afvragen waarom niet iedereen in het project geld krijgt is hetzelfde als jezelf afvragen waarom niet iedereen die meedoet in een loterij geld krijgt. Het overhandigd krijgen van een niet-simpel-te-factoriseren groot getal door de GIMPS kan je beschouwen als een 'lotnummer' waar je geld mee kan verdienen. Daarom doen veel mensen eraan mee.

Maar ze kunnen het tenminste aan een goed doel schenken.

DNA folding@home (zoeken naar oorzaken voor ziekten) en distributed zoeken naar medicijnen is mogelijk en slechts mogelijk door het pionierswerk dat the GIMPS verricht heeft. Hiervoor waren er voor zover ik weet geen wereldwijd gedistribueerde computernetwerken. De GIMPS heeft er verder veel moeite in gestoken - en naar ik aanneem ook geld.

[kidde]

Waarom krijgen mensen geld voor het vinden van iets waarvan men weet dat het bestaat?

Maf, maar in de 20+ antwoorden hierboven staat het juiste antwoord er nog niet 1x bij.

In de woorden van de 'prijsdonateurs' zelf:

"to encourage ordinary Internet users to contribute to solving huge scientific problems."

Het is een prijs ter stimulering van de wetenschap. Net zoals de Nobelprijs of de X-prize, of een nieuw element dat naar jou / jouw universiteit / woonplaats van die universiteit genoemd wordt omdat je een belangrijke bijdrage hebt geleverd aan de wetenschap. De huidige onderzoekers bij CERN krijgen waarschijnlijk ook de Nobelprijs voor het vinden van het Higgs deeltje, terwijl het al vrij zeker is dat dat deeltje bestaat en gevonden gaat worden.

Een voorbeeld voor de 'vooruitgang' die dit GIMPS project heeft opgeleverd wat Tweakers aan zou kunnen spreken (er zijn meerdere), is het méést (voor Intel proc in assembly geschreven) geoptimaliseerde programma ooit. Maar ook hoe je werk verdeeld over duizenden nodes die niet altijd 100% te vertrouwen zijn en waar je soms nooit meer iets van hoort omdat ze bijv. 'verdwijnen'.

[Proxy]

Omdat veel mensen niet gratis onderzoek willen doen

[Grannd]

Mensen weten ook dat er dino's hebben geleefd op aarde, maar degene die een ingevroeren dino in een nu smeltende ijskap vind zal ook een hoop geld krijgen...

[Anoniem: 399]

daarvan weet je niet of het bestaat

[Anoniem: 8504]

Niet als je dat per-sé niet wilt.. Je kan toch niet ontkennen dat dino's hebben bestaan? Dan zou het logisch gevolg zijn dat met een aan zekerheid grenzende waarschijnlijkheid we nog niet alle Dino Skeletten hebben gevonden..

Of begrijp ik je verkeerd?

[bdh]

... waarbij p ook een Mersenne-priemgetal is.

Dit is niet waar, p kan ieder natuurlijk getal zijn. Als p ook een Mersenne-priem zou moeten zijn is de definitie cyclisch.

De rij met priemgetallen is oneindig en er bestaat dus geen allergrootste priemgetal, aangezien er altijd een grotere te vinden is. Het aantal bekende Mersenne-priemgetallen is derhalve nog steeds groeiende

Er zijn oneindig veel priemgetallen. Maar dat impliceert niet dat er oneindig veel Mersenne-priemgetallen zijn zoals hier wordt gesuggereerd. Volgens mij is het nog onduidelijk of er een grootste Mersenne-priem is.

Wat betreft het nut, dat is er niet echt. Net als het miljardste cijfer achter pi is het meer leuk om te weten (voor sommige mensen). De priemgetallen die voor encryptie worden gebruikt hebben 'maar' honderden cijfers die je computer gewoon zelf zoekt, bovendien wil juist zo geheim mogelijke priemgetallen gebruiken

[Anoniem: 167279]

Uhh p hoeft geen mersenne-priemgetal te zijn maar mag zeker niet zomaar ieder natuurlijk getal zijn. p moet een priemgetal zijn!!

[BeQuietAndDrive]

Dit ontgaat mij geheel ben ik bang alleen de notatie al, 2P-1??

Maar definieer eens 'deelbaar door' want je kunt elk getal delen door elk ander getal, er komt altijd een uitkomst uit toch?

[Matis]

Niet als je kijkt naar delingen zonder restdeler. Dat is de voorwaarde van een priemgetal.

Je zutl geen getal vinden anders dan 1 en het getal zelve welke een deling oplevert zonder restdeler!

[Reactie gewijzigd door Matis op 23 juli 2024 18:46]

[BeQuietAndDrive]

Volgens mij kun je elk getal door 1 delen en door zichzelf, voorbeeld 8/1=8 en 8/8=1. Of klopt dat dan ook? EDIT: dit is ook door bijv. 4 deelbaar, wordt hieronder uitgelegd, ok duidelijk!

Nog een vraag, waarom halen ze die -1 er niet meteen vanaf? Dus in plaats van het getal te noteren en dan -1 erachter gewoon het getal noteren direct met de 1 eraf getrokken?

Ik probeer te leren hier

[Reactie gewijzigd door BeQuietAndDrive op 23 juli 2024 18:46]

[ATS]

Dat kan niet in deze notatie! Die 1 gaat er pas ná de machtsverheffing.
Elk getal is inderdaad deelbaar door 1 en door zichzelf, maar niet elk getal is alleen deelbaar door 1 en zichzelf. Dat zijn de priemgetallen. Een subset van die priemgetallen zijn de Mersenne-priemgetallen die dus de vorm 2ⁿ - 1 hebben. 5 is bijvoorbeeld wel een priemgetal, maar geen Mersenne-priemgetal.

[Reactie gewijzigd door ATS op 23 juli 2024 18:46]

[kidde]

Nog een vraag, waarom halen ze die -1 er niet meteen vanaf?

Nou, dat is het hele eiereten, waar het nou exact om te doen is. 2^P-1 is dus een afkorting voor een lang getal. Bijv: 2^97-1 is de afkorting voor
158456325028528675187087900671; een getal van 31 cijfers.

(2^43.112.609-1)-1 is dus de afkorting van een getal van meer dan 10 miljoen cijfers! Binair is dat ruwweg 30miljoen bits ofterwijl 4 megabyte.

Vroeger schreef men altijd die 8 miljoen cijfers (voor de vorige Mersenne-priemgetallen) volledig uit op een poster met lettertype 2.5; maar de laatste poster was al meer dan twee bij twee meter met dat lettertype geloof ik.

[Meijuh]

die 2^P levert altijd een even getal op. Als je er 1 van af trekt heb je een oneven getal, en iets zegt me dat oneven getallen veel minder delers hebben.

[ATS]

Precies. Elk even getal is op zijn minst deelbaar door 2. Even getallen, behalve 2 zelf, kunnen dus nooit een priemgetal zijn.

[Anoniem: 241040]

omdat een getal van de vorm 2^P nooit een priemgetal is, die 2^P-1 is immers niet het getal zelf maar hoe je er aan komt, bv stel dat P = 3 dan is die 2^P-1 = 7

[lammert]

Nooit wiskunde gehad ofzo? 8 kan je, behalve door 1 en 8, ook nog eens door 2 en 4 delen en is dus geen priemgetal, in tegenstelling tot bijvoorbeeld 7.

Als notatie van Mersenne priemgetallen wordt 2^p-1 gebruikt omdat het getal uit miljoenen cijfers bestaat. Het is een stuk handiger en sneller om zo'n enorm groot getal als een macht van 2 te schrijven met vervolgens -1 daarachter, dan om een getal van 12.978.189 cijfers neer te gaan kalken.

[mheikens]

De notatie van Mersenne vindt zijn origine in het binaire stelsel. Dat er nu toevallig naar enorm grote priemgetallen wordt gezocht, en de notitie zich daar voor leent is een bijzaak.

[ATS]

"Deelbaar door" betekent dat de uitkomst van die deling een geheel getal oplevert. Dat is de basis van het hele idee van priemgetallen: 4 is deelbaar door 2, maar 5 is alleen deelbaar door 1 en door zichzelf en is dus een priemgetal.

Die notatie is 2^P - 1. Dat superscript is belangrijk. Voor een wat inzichtelijker geheel: je hoeft voor P geen 43.112.609 te nemen, het is wellicht wat duidelijker te laten zien met 3:

2³ - 1 = 8 - 1 = 7. Een Mersenne-priemgetal dus. Met P = 4 werkt het niet, omdat 15, naast deelbaar door 1 en 15, ook deelbaar is door 3 en 5.

[FreezeXJ]

kleine correctie, de grap is hier dat p ook een priemgetal is. p=4 bestaat lekker niet (4 is nog geen priemgetal). Volgende in je reeks is p=5, wat 31 oplevert... Priem

[Krylinck]

Ja, een kommagetal. En dat is dus net waar ze niet naar zoeken. Een priemgetal is een getal wat alleen deelbaar is door 1 en door zichzelf. Als je het door een ander getal deelt, komt er een kommagetal uit. Men definiëert "deelbaar door" dus als delen waar een geheel getal uit komt. Er komt dan dus niet altijd een oplossing uit. Het is net als op de basisschool: 49 delen door 5 geeft 9, rest 4.

2P-1 is trouwens (2 tot de macht x) - 1. Dat is een handige notatie, want dan hoef je niet het hele getal te noteren. Iets wat me trouwens al verrekte lastig lijkt met 12.978.189 cijfers. Daarom schrijven ze het liever als (2^P)-1.

[Meijuh]

Ja maar geen geheel getal;) en dat is de essentie van een priemgetal

[Nouky]

'deelbaar door' = resultaat is een geheel getal indien gedeeld door 1 en zichzelf. Indien gedeeld door een ander getal krijg je idd een uitkomst, maar dit zal dan geen geheel getal zijn.

[TwistedAnimator]

en waarom alleen zij als de hele wereld meegezocht heeft (distributed)?

[BtM909]

Omdat het wellicht mensen aanzet om mee te helpen met CPU beschikbaar stellen?

Zie ook: http://www.mersenne.org/prize.htm. Het geld wordt trouwens ter beschikking gesteld door Electronic Frontier Foundation

[Reactie gewijzigd door BtM909 op 23 juli 2024 18:46]

[ARNI]

Omdat zij het hebben gevonden en de rest van de wereld niet?

[Aikon]

Omdat het niet zo motiveert als je iedereen 50 cent geeft, een grote prijs is veel aantrekkelijker.

[elmertje]

2p-1, waarbij p ook een Mersenne-priemgetal is. De eerste Mersenne-priemgetallen zijn 3, 7, 31, 127 en 8191.

Huh. Hoe krijg je 3 dan? Die 7 dat lukt wel (je vult 3 in voor p). Klopt dat wel? Is 7 dan niet de eerste?

[martijnve]

het moet zijn 2^p-1

[elmertje]

ja dat snap ik ook wel. Leg jij me aub uit waarom 3 een mersenne priemgetal is.
edit: @ blackangel: precies !!

[Reactie gewijzigd door elmertje op 23 juli 2024 18:46]

[SRI]

p hoeft geen priemgetal te zijn. p moet gewoon een geheel getal zijn.

(2^P)-1 is redelijk simpel
P = 1 geeft 1 (telt niet moet groter dan 1)
P = 2 geeft 3 (4-1)
P = 3 geeft 7 (8-1)
P = 4 geeft 15 (16-1) Deze mag niet omdat 15 meerdere delers heeft naast 1 en zichzelf te weten namelijk 3 en 5.
P = 5 geeft 31, die mag weer wel.
En naarmate je verder gaat krijg je steeds vaker dat er meerdere delers zijn (groter getal is meer mogelijkheden op meerdere delers).
Wat mij verbaasd is dat dit in principe wiskunde is en er dus hoogstwaarschijnlijk een formule voor zou moeten zijn. Maar dat laat ik aan de hoogbegaafde wiskunde genieën over.

[Upquark]

p moet wel een priemgetal zijn, zie http://en.wikipedia.org/wiki/Mersenne_prime voor een korte uitleg waarom.

In het kort: als p geen priemgetal is (maar bijv. te ontbinden in a*b), is 2^p-1 te ontbinden in factoren:

2^(a*b)-1 = (2^a-1) * (1 + 2^a + 2^(2a) + 2^(3a) + ... + 2^((b-1)*a)

Bijvoorbeeld:

2^6-1 = (2^2-1) * (1 + 2^2 + 2^4)
63 = 3 * (1+4+16)
63 = 3 * 21

[Reactie gewijzigd door Upquark op 23 juli 2024 18:46]

[Caelorum]

drie is alleen deelbaar dor 3 en 1?
2^2-1=4-1=3?
2 is een priemgetal omdat het ook alleen deelbaar is door 2 en 1

dus is 3 ook een mersenne priemgetal

[Reactie gewijzigd door Caelorum op 23 juli 2024 18:46]

[ATS]

2² -1 = 3. Zo moeilijk is die toch niet?

[Reactie gewijzigd door ATS op 23 juli 2024 18:46]

[blackangel]

Nee hoor. 2^n-1, met n als priemgetal, En daarmee niet per definitie Mersenne priemgetal. Een foutje in de tekst dus.

[ATS]

Nee, in Mⁿ = 2ⁿ - 1 hoeft n zelf geen priemgetal te zijn om de M_n een Mersenne-priemgetal te laten zijn. Voor elke waarde van n is M_n een Mersenne-getal, als dat een priemgetal is, is het dus een Mersenne-priemgetal.
Bovenstaande klopt niet. Het is wiskundig bewezen dat als M_n priem is, n zelf dat ook is. Andersom niet trouwens.

[Reactie gewijzigd door ATS op 23 juli 2024 18:46]

[blackangel]

Ik durf het niet hard te beweren, maar volgens wikipedia is er bewezen dat wanneer voor p=2^n-1 een priemgetal is, dan is n ook een priemgetal. Ik weet niet of het voor de definitie van een Mersenne-priemgetal van belang is of n een priemgetal is, maar er bestaan (schijnbaar) geen uitzonderingen.

[PiepPiep]

Dat bewijs is simpel, als de n in 2^p-1 een factor q heeft dan is 2^p-1 deelbaar door 2^q-1
Voorbeeld :
2^15-1 = 32767
2^3-1 = 7
2^5-1 = 31
32767 / 7 = 4681
32767 / 31 = 1057

[airell]

uh... 2^p -1

voor p=2, 2^2-1 = 3.

[elmertje]

2 is geen mersenne priemgetal....laat staan uberhaubt een priemgetal.....

[Pensacola]

2 is wel degelijk een priemgetal (het enige even priemgetal)

[lembregtse]

Euhm wat? http://nl.wikipedia.org/wiki/Priemgetal

[elmertje]

uh, ja natuurlijk.....(omdat ie even is had ik 'even' een brainfuck) maar punt blijft, dat het geen mersenne priemgetal is. dus dan nog een foutje in de tekst. (toch)

[Krylinck]

Priemgetal:
2 / 1 = 2
2 / 2 = 1
Dus je deelt hem alleen door 1 of door zichzelf, want anders krijg je geen geheel getal. 2 is dus wel een priemgetal.

Mersenne-priemgetal:
(2^1)-1 = 1
(2^2)-1 = 3
Dat dus niet. Daar heb je gelijk in.

[Anoniem: 140111]

a) 2 is alleen deelbaar door zichzelf en 2 en is daarmee het enige even priemgetal.
b) n hoeft geen Mersenne te zijn.

[Reactie gewijzigd door Anoniem: 140111 op 23 juli 2024 18:46]

[? ?]

(2 tot de 2e macht)-1 = 3
2 is ook een priem

[Anoniem: 89602]

p=2
2^2 = 4
4 - 1 = 3

edit: crap ik lul uit me nek: 2 is geen Mersenne

[Reactie gewijzigd door Anoniem: 89602 op 23 juli 2024 18:46]

[elmertje]

ja, precies dat bedoelde ik ja.

[lammert]

Huh. Hoe krijg je 3 dan? Die 7 dat lukt wel (je vult 3 in voor p). Klopt dat wel? Is 7 dan niet de eerste?

Vergeet niet dat 2 ook een priemgetal is:
2²-1= 4-1= 3