Priemgetal van zeven miljoen cijfers berekend

New Scientist laat wederom zien hoe het samenvoegen van gedistribueerde rekenkracht kan leiden tot vorderingen van de wetenschap. Het Great Internet Mersenne Prime Search-project (GIMPS) heeft er namelijk toe geleid dat een Mersenne-priemgetal met zeven miljoen cijfers is gevonden: 2^24,036,583 -1. Deze categorie priemgetallen voldoet niet alleen aan het criterium slechts perfect door zichzelf en door 1 deelbaar te zijn, maar is bovendien van de vorm 2^p-1, met p ook een priemgetal.

Eerder werden al veertig andere Mersenne-priemgetallen gevonden. Behalve dat het een leuke wiskundige curiositeit is, worden priemgetallen ook zeer vaak toegepast in het beveiligen van data met cryptografie. Ondertussen gaat de zoektocht naar een Mersenne-priemgetal met tien miljoen decimalen nog door, waarbij de ontdekker een prijs van 100.000 dollar te wachten staat.

Reacties (125)

[Mercarra]

Men neme 2 heel hoge priemgetallen. Die vermenigvuldig je. Dan heb je een getal dat deelbaar is door enkel die 2 priemgetallen. Alleen jij weet deze. Anderen doen er jaren over om achter te komen. Zo werkt die versleuteling ongeveer... dacht ik.

[Donderwolk]

Klopt. Deze methode wordt dan ook voornamelijk toegepast bij public key encryption (assymetrische encryptie). Bij public key encryption wordt een sleutel in twee delen verdeeld. Een publiek en een privé gedeelte. Deze twee delen inverteren elkaars werking. Wat je dus met het ene gedeelte encrypt kun je met het andere gedeelte weer decrypten.

Het publieke deel van de sleutel dat je verstuurt en wordt door anderen gebruikt om data mee te versleutelen. Jij kan de data dan ontsleutelen met je eigen privé gedeelte van de sleutel dat je zelf in je bezit houdt. Dit encrypten en decrypten van de data gaat dan met behulp van (zeer grote) priemgetallen op een soortgelijke wijze die jij beschreef.

[mjtdevries]

En worden daarbij dan ook inderdaad priemgetallen met 7 miljoen decimalen gebruikt of is dat gewoon grote flauwekul?

[hardwareaddict]

Nah met rond de 704 bits zit je vrij safe al.

Je kunt 20000 dollar verdienen door n = iets meer als 700 bits te factoriseren.

Aan die priemgetallen valt weinig te verdienen zo gok ik. Heb de regels natuurlijk direct gecheckt en kwam tot conclusie dat het ging om het *bewijzen* van dat je getal een priemgetal is. Echt 100%.

Opmerking bij zulke enorme getallen van 10 miljoen digits is de kans dat na een paar pseudo priemgetal testen iets nog een composite is vrijwel 0.

Echt de kans dat het een priemgetal is dat is wel iets van rond de

99.99999999999%

Maar dat is niet genoeg om dus dat geld te verdienen van 100k dollar.

Ze willen een keihard bewijs dat het een priemgetal is, met je source code erbij.

Dat bewijs is dus vrij lastig, dat laatste nog lastiger

[.oisyn]

Kleine aanvulling op het stukje van [#]Thunderstorm:

Het kan ook andersom: je versleutelt zelf een bericht met je eigen private key, en je stuurt dat naar iemand anders. Iedereen kan dat ontcijferen omdat iedereen in principe jouw publieke sleutel weet. Het doel is dan echter niet encryptie, maar authenticatie. Omdat jij de enige bent die jouw private key heeft, weet iemand anders dus zeker dat het bericht van jou afkomstig is als hij het met jouw public key kan ontcijferen.

[Verwijderd]

maar is bovendien van de vorm 2p-1, met p ook een priemgetal.

Wat betekent dat?

[XyritZz]

Het is van de vorm 2^(p)-1. Waarbij p ook een priemgetal is.

Betekent dus dat in 2^(24.036.583)-1, daarin is 24.036.583 ook een priemgetal. Je vult dus voor de macht van 2 een priemgetal in, haal er daar nog één vanaf, en je komt dan weer op een priemgetal uit.

[Kees]

Dat betekent dat je twee tot de macht p verheft en van dat getal er 1 aftrekt.

Bijvoorbeeld voor p = 3 (3 = priemgetal) geldt: 2^3 -1 = 8 - 1 = 7 hetgeen ook weer een priemgetal is. Dit voorbeeld is nog uit je hoofd na te rekenen, maar voor het priemgetal dat ze gevonden hebben heb je dus een 240,36,583 bits computer voor nodig om het in een integer weer te kunnen geven

[losealot]

das het tweede mersenne priemgetal op een half jaar tijd...
en toch zitten ze nog maar aan 40.
weet iemand hoelang ze hier al mee bezig zijn??

[jesternl]

Het originele programma heet prime95, dus iik denk sinds 1995. Ik heb het in 96 een tijdje gedraaid, dus *zeker* sinds die tijd.

[Verwijderd]

Correctie aan de 41ste
http://www.mersenne.org/

[Munters]

Maar je kunt het wel weer heel effectief zippen, zo'n rij van 24036583 binaire eentjes...

[boner]

nee een binair een willekeurig aantal enen en dan een nul is altijd een even getal in het decimale stelsel.

[GeeBee]

volgens mij is 2^24036583 -1 binair 24036582 enen en dan een 0

[Verwijderd]

nee...onzin...zip de schrijftaal

past in enkele bytes dan...

2^24036583-1

en bij het uitpakken laat je de computer het berekenen. ;-) (veel succes)

[eggieman]

@GeeBee :
tuurlijk niet dan istie deelbaar door 2 (10 binair)

edit
duidelijk gemaakt dat ik reageer op GeeBee
Maar dat had Boner ook al gedaan zie ik nu
\edit

[.Frank]

Dit wil zeggen dat de factor waarmee twee wordt vermenigvuldigd zelf ook een priemgetal is.

[gday]

Het is niet de factor waarmee vermenigvuldigd wordt, maar de macht.

[KatirZan]

dat vind ik een machtige factor! :y)

[ekx]

[frustreermodus]
Die priemgetallen blijven me achtervolgen...

Had te weinig tijd om in vba in acces priemgetallen te berekenen tussen 300 en 500... argl (yup regentaat niveau informatica... hoog é ^o^

En nu weer????

ARGGLLLLLLL

Wanna stick dynamite in that guys ass who post this newspost...


[/frustreermodus]

Nu eerlijk... hoe komt het dat priemgetallen gebruikt worden bij encryptemodussen? om zo de kans uit te sluiten dat het nog door een ander getal deelbaar is ook? Redeneer ik juist?
Dus een groot priemgetal, is dus een factor van betere encryptie...

Nu vraagje, worden die priemgetallen nie bijgehouden in een lijst? als dat zo is, is't breken van een encryptie toch gemakkelijker dan gedacht, of redeneer ik totaal verkeerd?


EDIT

HOEZO OVERBODIG? ik stel hier toch een belangrijke vraag?

[Brons]

Volgens mij zat het zo: je neemt 2 priemgetallen die jij alleen weet. Die vermenigvuldig je. Het kost dan iemand heel veel computerkracht en tijd om de sleutel te achterhalen

edit:

^^ laat, mercarra was 4 minuten eerder

[Verwijderd]

Priemgetallen worden gebruikt bij encryptie omdat er geen pijl op te trekken valt, maw, ze zijn volstrekt willekeurige getallen.
Er valt geen formule op te stellen om priemgetallen uit te rekenen. De formule van Marselle gaat ook niet altijd op.

[hardwareaddict]

Priemgetallen worden gebruikt omdat het product van 2 priemgetallen bijna niet te factoriseren is als de factoren genoeg groot zijn.

Dus het is relatief simpel om 2 grote priemgetallen te genereren en te komen tot het enorme getal :

458639894740177872203851888882880876067241969173601509119850773421075033531
911952091884308235496915335374976647492410372909657772417102384827434795295
8239511223585023871547701371676310816967976474482639785439929 (211 digits)

Maar als je iemand anders dit getal laat zien dan zal deze het niet snel weten te ontbinden in factoren.

[Verwijderd]

ja er worden priemgetallen gebruikt, op google vind je gerust genoeg informatie over encryptie etc

gebruikt DES of blowfish niet toevallig zoiets?

[zeroxcool]

De schrijver van dit item heeft hier een goede 3 jaar geleden hier een heel handig artikel over geschreven. Ik heb het nog gebruikt toentertijd om mijn profielwerkstuk op de HAVO mee aan te vullen. Erg leuk om eens door te lezen mocht je geïnteresseerd zijn in wiskunde en cryptografie:
http://www.tweakers.net/reviews/189

Overigens wordt een priemgetal wat met 2^p - 1 ook een priemgetal vormt, een Mersenne-priemgetal genoemd. Wat daar weer de bedoeling achter is kun je met Google wel vinden .

[Verwijderd]

Waar staat dat priemgetal ? vorige keer kon je dan downloaden. (en nakijken )

[Thomson]

Hier staat ie

http://mersenne.org/prime7.htm

[N0 0B]

zo lekker 3,5 mb zip aan getallen
txt bestand is +- 7 mb

[gp500]

Had ook even een verwijzing naar DPC bij gekunnen

[MarcyDarcy]

hee vooral van jou een leuke geste
maar mijns inziens hoeft dat niet hoor. DPC heeft geen alleenrecht op zulke posts, kan best een nieuwsposts over een DC project zijn zonder dat er gelijk vermeldt moet worden dat DPC ook bestaat.
Daarnaast is DPC niet echt actief bij het GIMPS project dus wat dat betreft past het ook niet bij het nieuwsbericht.

Ofwel gewoon zo laten en af en toe nog zulke nieuwsposts

[Freee!!]

Het zou pas echt stoer zijn als 24,036,583 zelf ook een Mersenne-priemgetal is.

En ik vraag me af of 2^ (2^24,036,583) -1 ) -1 ook weer een Mersenne-priemgetal is, maar het zal nog wel even duren voordat dat uitgerekend is.

EDIT:
Oeps, de vraag is vooral of het een priemgetal is, zo ja dan is het door de definitie automatisch ook een Mersenne-priemgetal.

[Verwijderd]

even in vatbare getallen
zoiets als 127 (2^7-1)
waarbij 7=(2^3)-1
en 3=(2^2)-1
en 2=(2^1)-1

de volgende zou dus (2^127)-1 zijn hopende dat dat een priemgetal is

[Verwijderd]

Volgens mijn scientific rekenmachientje is 2^127 geen priemgetal:
2^127 =
170.141.183.460.469.231.731.687.303.715.880.000.000
vervolgens dit getal gedeelt door 2:

85.070.591.730.234.615.865.843.651.857.942.000.000

Maar het kan ook zijn dat mijn rekenmachientje een afrondingsfoutje maakt.

misschien heeft er iemand Mathcad of een ander Software programma wat met zulke complexe getallen kan omgaan.

Er zit wel logica in je verhaal dus het zou zomaar kunnen kloppen.

[Eärendil]

Volgens bc (een UNIX rekentooltje) is het:

2^127-1=170.141.183.460.469.231.731.687.303.715.884.105.727

Het delen door 2 wat jij doet slaat nergens op, dat is natuurlijk 2^126. Het mersenne-priemgetal is (2^p)-1, niet 2^(p-1) (dat is namelijk geen priemgetal, want deelbaar het is door twee)

[Verwijderd]

[overbodig]

Klopt, ik was er niet helemaal bij

[/overbodig/]

[Red Lion]

@ Pandora:
Bij mijn weten is 2 niet (2^1)-1 (nofi)

@Jeroen111:
Dat is zekerweten een afrondingsfout: 2^x komt als laatste cijfer altijd een van de volgende cijfers uit (ook in die volgorde): 2, 4, 8, 6, 2, 4, 8, 6, etc...

[Janoz]

Is het helaas niet. (eerste dan) In dat geval had p 24.52 (= 2log(dat getal)) moeten zijn, en dat is geen geheel getal.

[Verwijderd]

wat ik niet snap is dat ze FFT gebruiken om priemgetallen te verifyeren.. ik zou denken dat je toch echt gewoon botweg moet delen (hoewel alleen de modulus al voldoende info geeft, maar dat is geloof ik nagenoeg dezelfde berekening, kost ieg net zoveel tijd).. snap totaal niet hoe je dat met fast fourier zou kunnen optimaliseren.
nouja, ben nooit zo'n held in wiskunde geweest

[Domokoen]

Met de FFT kan je polynomen efficient vermenigvuldigen: in O(n log n) tijd ipv O(n^2). Voor grote getallen maakt dat heel veel uit
Als je je afvraagt: ik had het toch over delen? Klopt, maar vermenigvuldigen is het omgekeerde van delen, ze werken vanaf de andere kant.

[eggieman]

2 ^ 24,036,583 je moet tot de wortel van een getal voor bepaling oftie priem is of niet: dus
de helft van de exponent.
2^ 12.018.291 * Wortel 2 Dan kun je de 2 vouden weghalen dat scheelt de helft dan wordt het 2^12.018.290 berekeningen. (Als je het slimmer doet kun je het nog verder beperken tot bijv 7 van de 30 getallen testen. Dit laatste geeft 2^6.875.964 berekeningen = 10^22. Je processor draait op max 3 * 10^9 Mhz. Stel dat je hem elke clocktick zo'n berekening zou kunnen laten doen kost dat 10^13 seconden = 317.097 jaar.(schikkeljaren niet mee gerekend)

En dan heb je nog dat zo'n processor vele instructies per berekening moet doen. Processors zijn tegenwoordig max 64bit ipv 24.036.583bit

[martijnvanegdom]

Helaas,
De officieële defeinitie van een mersenne:
2^n -1 waarbij n een gehele integer is. RSA maakt gebruik van priemgetallen, maar niet van mersenne, anders is het net weer wat makkelijk te kraken.

Verder is er geen systematiek in de priemgetallen, of mersenne priemgetallen te vinden, echter er zijn wel oneindig veel priemgetallen: dat bewijs loopt als volgt:

Stel ik er zijn eindig veel priemgetallen:
3,5,7...P.. Als je ze allemaal vermenigvuldigd en er één aftrekt, dan is dat niewe getal niet te delen door een van je priemgetallen. Dus dat nieuwe getal moet ook weer priemgetal zijn. (en ja, alle getal zijn te delen door priemgetallen behalve als ze priemgetal zijn)

[Verwijderd]

offtopic:
Er zit wel systematiek in de opvolging van priemgetallen. Deze wordt echter niet gedefinieerd door de priemgetallen zelf, maar eerder door de composieten die als uitzondering gelden.

priemgetallen heb je in twee variaties (getallen 2 en 3 uitgezonderd) namelijk 6n+1 en 6n-1

Maar niet alle getallen die daaraan voldoen zijn automatisch priem. 25 en 35 zijn daar voorbeelden van.

Deze uitzonderingen tonen (als je weet hoe ) een huisvast systeem van opvolging.

[.oisyn]

Ik vind dat van die 6n-1 en 6n+1 maar een kromme redenatie. Wat je daarmee eigenlijk zegt is dat een getal niet deelbaar door 2 of 3 mag zijn. En dus alle getallen niet deelbaar door 2 en 3 zijn mogelijke kandidaten. Dat is natuurlijk waar, maar wel een loos argument

Als je puur kijkt naar getallen die deelbaar zijn door 2, dan is in de reeks 0,1,2,3,4,... het eerste getal wel deelbaar door 2, die daarna weer niet, daarna weer wel, daarna weer niet, daarna weer wel, etc.

Dan kijk je naar de getallen die deelbaar zijn door 3. Dan krijg je dus: wel, niet, niet, wel, niet, niet, wel, niet, niet, ...

Als je dat weer combineert met die van 2, dus alle getallen die deelbaar zijn door 2 of 3, dan krijg je: wel, niet, wel, wel, wel, niet, wel, niet, wel, wel, wel, niet. Oftewel, steeds de 1e en de 5e niet als je het getal modulo 6 neemt, en dat is precies wat je bedoelt met 6n-1 of 6n+1, namelijk alle getallen niet deelbaar door 2 of 3.

Maar daar kun je de reeks van 5 ook weer bij betrekken, waardoor je de reeks van modulo 30 neemt. Feitelijk kun je dan zeggen dat alle priemgetallen, met uitzondering van 2, 3 en 5, één van de volgende vormen hebben: 30n+1, 30n-1, 30n+7, 30n-7, 30n+11, 30n-11, 30n+13, 30n-13.
Dus dat zijn alle 6n-1 en 6n+1 getallen, maar dan zonder de getallen die ook nog eens deelbaar zijn door 5 (door 30n+5 en 30n-5 weg te strepen).

En dan kun je alle getallen deelbaar door 7 ook nog eens wegschrappen, en dan krijg je heel veel combinaties modulo 2*3*5*7 = 210, waar vrij gemakkelijk achter te komen is, maar ik heb nu geen zin om dat uit te schrijven

[Verwijderd]

Jeetje....wat ben jij omslachtig als je wat probeert uit te leggen zeg

Misschien moeten we hier maar een apart topic over openen, want deze discussie is zo geen lang leven beschoren...en het onderwerp is zo boeiend.

Anyways: ik snap je punt wel, maar je gaat een beetje voorbij aan mijn stelling.

Martijn zei dat er geen logisch orde der priemgetallen is, waar ik het niet mee eens ben.

Ik heb niet verzonnen dat alle priemgetallen van de vorm 6n+/-1 zijn, dit is nou eenmaal zo.
Dat je dat ook kan uitschrijven op jouw uitvoerige wijze ben ik met je eens.

Mijn punt was echter dat er uitzonderingen op die regel zijn (na een tijdje meer uitzonderingen dan niet)
en dat die WEL een regelmatig patroon vormen.

En doordat daar een patroon vormt kan je dus andersom ook beredeneren wanneer iets wel of niet priem is aan de hand van het patroon van uitzonderingen. Overigens is deze manier van priemgetallen vinden behoorlijk omslachtig en vergt veel processor kracht, maar t werkt wel.

Overigens heb ik nog nooit iemand gehoord die dit patroon ook ontdekt heeft, dus misschien ben ik wel de eerste....

Mocht je dit lezen en het nog steeds niet met me eens zijn, open dan maar een topic met de naam Orde der Priemgetallen, dan praten we nog even verder....

....zoals ik al zei, tis een boeiend onderwerp !!

[ginamri]

in een woord w00t. Mijn enigste vraag is, "Hoe test men een getal dat zo ontzettend groot is of het dan ook daadwerkelijk een priemgetal is". Ik vraag dus naar een efficiente methode die dus niet voorspelt of het een priemgetal is maar 100% accuraat is.

[Janoz]

De enige manier is om alle getallen bijlangs te gaan tot 2^24,036,582 en kijken of je (2^24,036,583)-1 kan delen door dat getal.

[StefSybo]

Nee hoor je hoeft "maar" tot de wortel van het getal door te gaan, als er geen deler is die kleiner is dan de wortel van het getal, is er ook geen die groter is dan de wortel (als je kan delen door een getal dat groter dan de wortel is, is de uitkomst van die deling kleiner dan de wortel, dan zou je ook door dat getal moeten kunnen delen).
Dit is trouwens geen erg efficiente methode (in elk geval totdat we quantumcomputers hebben), dus waarschijnlijk gaat het anders.

[wout]

Als je alle getallen langsgaat, hoef je volgens mij nooit verder dan de vierkantswortel uit dat getal. Anders wordt de tweede factor kleiner en die heb je dan al gehad...

<EDIT>StefSybo, je was met net voor</EDIT>

[Munters]

Er zijn specifieke testen die alleen opgaan voor Mersenne-priemgetallen. Dat is dan ook meteen de reden waarom die hele grote priemgetallen altijd van dit specifieke type zijn.

[Verwijderd]

Met het Lucas-Lehmer algoritme:

s(0) = 4
s(n) = (s(n-1) ^ 2 - 2) mod 2^M - 1

M is een Mersenne-getal <=> s(M-2) = 0

Voor M=7:

s(0) = 4
s(1) = 4*4-2 mod 127 = 14
...
s(5) = 111*111-2 mod 127 = 0 dus 2^7-1 is een priemgetal

[XyritZz]

Ben ik nu zo stom, of kun je dan ook gewoon:

2^(224,036,583-1) -1 doen...... Of is het dan niet zeker dat je op een priemgetal uitkomt??

[Verwijderd]

Als dat zo was hadden ze al die pc's niet nodig

[Verwijderd]

Nee, dit kan niet. De adder onder het gras bij priemgetallen van Mersenne is, dat zijn regel (2^(p)-1=priemgetal) niet altijd opgaat. Vaak wel, bijvoorbeeld bij:
2^5-1=31
Maar bij
2^11-1=2047
gaat de regel bijvoorbeeld niet op, want 2047 is deelbaar door 23.

[slager]

Over stom gesproken...

Er staat 2^p - 1, dus (2 tot de macht p) - 1. Voor jouw getallenvoorbeeld is dit dus 2^5 - 1 = 31. Dit is wel degelijk een priemgetal.

[Fuzzillogic]

Nee, gij

het is niet 2*5, maar 2^5.

[Verwijderd]

Dan kan je op een even getal uitkomen en die is vervolgens weer deelbaar door 2 waardoor het geen priemgetal is.

[slager]

Uhum, dat klopt dus niet. Alle exponenten van 2 zijn per definitie even getallen. Trek je daar 1 vanaf, dan kom je dus altijd op een oneven getal uit.

[Freee!!]

Reken nog maar eens na, je komt echt niet op een even getal uit hoor.

[Verwijderd]

Leesfout

[PipoDeClown]

het gaat erom dat je het ook bewijst

[Verwijderd]

http://www.utm.edu/research/primes/largest.html#biggest een lijstje van de grootse priemgetallen het grootste niet mersenne priemgetal is er een van de vorm k *2^n+1 door http://www.seventeenorbust.com/ gevonden maar niet door een DPC'er op zoek naar roem.
Maar door iemand die schreef.'' I am proud to be a part of Team ExtremeDC! We are Cow Killers!!! ''