Distributed computing ontdekt 44ste Mersenne-priemgetal

In 2003 ontdekte een 26-jarige student het grootste priemgetal ooit en een jaar later slaagde men er met een 'distributed computing'-project in een Mersenne-priemgetal van zeven miljoen cijfers te berekenen. Mersenne-priemgetallen zijn speciaal omdat ze niet alleen deelbaar zijn door zichzelf en door 1, maar bovendien van de vorm 2^p-1 zijn, waarbij p ook een priemgetal is. Nu zijn wetenschappers van de Central Missouri State University erin geslaagd het grootste priemgetal ooit en in een klap ook het vierenveertigste Mersenne-priemgetal te berekenen, met als waarde 2^32.582.657-1.

Het getal telt 9.808.358 cijfers en daarmee hebben de onderzoekers bijna de kaap van tien miljoen cijfers gerond. De Electronic Frontier Foundation heeft namelijk een beloning van 100.000 dollar uitgeloofd voor de eerste die erin slaagt een priemgetal van die grootteorde te vinden. Het team uit Missouri is overigens aangesloten bij het Great Internet Mersenne Prime Search-project, dat er zich toe verbonden heeft 25.000 dollar van het prijzengeld aan een goed doel te schenken als een van hun leden erin slaagt de 100.000 dollar binnen te slepen. De koetjes van DPC zullen zich moeten reppen als ze nog kans willen maken op deze bonus.

Reacties (79)

[boe2]

Kan iemand me even verduidelijken hoe dit priemgetal nuttig gebruikt kan worden? Ik ben geen wetenschapper, dus kan er goed naast zitten, maar dit lijkt me niet veel nuttiger dan dat SETI project.

[Zwartoog]

Wiskundigen vinden het nou eenmaal leuk om getallen met een bepaalde eigenschap te onderzoeken en te vinden. Zo zijn Mersenne priemgetallen verbonden met 'perfecte getallen'.

Dus als M=2^p-1dan is M(M+1)/2 een perfect getal. Een perfect getal is dan weer de som van z'n delers (dus 6 = 1*2*3 = 1+2+3). (bron: wikipedia).

En tsja, wat je hier dan weer mee moet? Hetzelfde dachten ze duizenden jaren geleden waarschijnlijk over priemgetallen, welke nu noodzakelijk zijn voor goede versleutelingen e.d. Het nut van een wiskundige ontdekking komt vaak eeuwen later pas aan het licht.

[Frank-L]

M(M+1)/2 kan natuurlijk nooit een perfect getal zijn: het is niet eens een geheel getal.
M maal M+1 is namelijk altijd oneven.

[Anoniem: 131806]

Dit lijkt op een lapsus

3*4 lijkt even
4*5 ook eigenlijk

Ik begin iets te vermoeden...

[Anoniem: 92469]

Helaas, oftewel M is even of M+1 is even. Je vermenigvuldigt dus altijd met een even getal. Gevolg is dat je altijd een even getal als antwoord krijgt. Delen door 2 kan dus prima en levert weer een geheel getal op.

[Frank-L]

ehhh.... inderdaad, stom van me

[Nick The Heazk]

Priemgetallen worden gebruikt bij bv. SSL. Zowat alle encryptietechnieken baseren zich op priemgetallen. Dit heeft te maken met een aantal algebraïsche eigenschappen van het modulo-rekenen (met betrekking tot priemgetallen) waardoor men om de boodschap te kunnen ontcijferen op een bepaald punt een semi-priemgetal van zo'n 300 cijfers moet gaan ontbinden in priemfactoren. Op dit moment duurt dat nog steeds een aantal miljarden jaren (omdat het semi-priemgetal bestaat uit twee priemgetallen van elk 150 cijfers) waardoor het decoderen van zo'n boodschap feasible is. De persoon met de geheime sleutel kan dit echter wel snel ontcijferen omdat de geheime sleutel één van deze 2 priemgetallen is (als ik me niet vergis - de ontvangende persoon kan in ieder geval de Euler fi coëfficiënt berekenen waardoor hij/zij deze kan inverteren en aldus de boodschap kan ontcijferen).

Edit: @ Hieronder: ik zat er een factor 1 miljoen naast ! (ben het eventjes gaan checken)

[Seal64]

Dat kan natuurlijk niet, hè? 150 miljoen cijfers... Dat artikel is duidelijk genoeg, dit is tot nu toe het grootste priemgetal dat ze ooit uitgecijferd hebben, en dit heeft nog geen tien miljoen cijfers.

[Zoufiax]

Priemgetallen worden gebruikt in de cryptografie.

RSA is een voorbeeld van een asymmetrische versleuteling. Deze methode maakt gebruik van het feit dat voor het ontbinden van getallen in priemgetallen geen snelle methode bekend is als de priemgetallen voldoende groot zijn.

Bron (Wikipedia).

[eltorro]

Hmm, zat net iets te lezen op wiki over relatief prieme getallen,..
Schijnt dat tandwielen die tegen elkaar draaien en een aantal tanden heeft die relatief priem zijn, op bepaalde punten slijtage tegengaan,.. Op zich best nuttig lijkt me,..

Bron

[Anoniem: 175233]

En je denkt dat dit grootste priemgetal daarvoor nuttig gebruikt kan worden?

[Anoniem: 6882]

wie weet waar we met nanomechanica allemaal tegen aan gaan lopen

[Anoniem: 163134]

Dit kan bijvoorbeeld gebruikt worden voor encryptie in het jaar 2025 of zo?

Edit: Zwartoog was een tikkeltje sneller voor die encryptie-verwijzing...

[kidde]

dit lijkt me niet veel nuttiger dan dat SETI project.

Je vergeet dat ALLE distributed-computing projecten zoals SETI, BOINC enz. allemaal mogelijk zijn gemaakt door dit eerste distributed computing project. De GIMPS heeft dan ook aangetoond dat distributed computing projecten over internet mogelijk zijn. Daardoor kunnen onderzoekers nu gratis CPU-tijd verkrijgen voor onderzoek naar ziekten enz.

Tevens heeft het ook het (voor Intel procs) meest geoptimaliseerde computerprogramma (na 1990) ter wereld opgeleverd.

Nu is bewezen dat het idee en de software werken, is het project idd misschien iets minder nuttig. Het is nog altijd handig voor stress-testen na overclocken (Prime95 torture test), en benchmarken.

[Anoniem: 177275]

Lees dit maar eens:

http://nl.wikipedia.org/wiki/Illegaal_priemgetal

[Vincenz0]

Mooi werk koetjes!!!

Nu meer power in de UD Grid Cancer Project stoppen!
dat is teminste wat meer nuttig.

[airell]

...daar heb je volkomen gelijk in...

[stappel_]

grid loop al meer dan 3 jaar en er is nog niks uit gekomen behalve een aantal onderzoekers die zegt dat alles er veel belovend uit ziet.

ja echt nuttig dat grid.

[increddibelly]

Nee is ook een antwoord. dan weet je dat je iets anders moet proberen.

[Cowboy op zee]

Misschien moet je in de politiek gaan, daar worden ook vooral zaken die binnen 4 jaar - voor de volgende verkiezingen - zichtbaar nut hebben belangrijk gevonden.
Aan de andere kant (@Vincenzo0): wie weet wordt in de toekomst kennis die met het zoeken naar en vinden van priemgetallen is opgedaan wel nuttig toepasbaar bij kankeronderzoek.

[badflower]

volgens mij zijn de koetjes hard bezig, maar gezien het nieuwsartikel tot nu toe niet erg succesvol in deze categorie.

Ik vind het leuk dat je ze aanmoedigt daar niet van!

[Anoniem: 144629]

9.808.358 cijfers!!! Hoe bepaal je in godsnaam dat dat écht een priemgetal is, dus dat er niet een of ander paar idioot grote getallen is waardoor je dat zogenoemde priemgetal wél kunt delen? Gewoon alle mogelijke combinaties uitproberen? Zelfs een supercomputer is daar toch nog wel even zoet mee....

[moto-moi]

Zelfs een supercomputer is daar toch nog wel even zoet mee....

Waarom denk je dat er op t.net over gepost is? Juist omdat het zo'n grote prestatie is

[Baritee]

Maar hoe bewijs je dat het een priemgetal is?

[RickDeckard]

met een priemtest?

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

[kidde]

Nee, met een Lucas-Lehmer test. Een priemtest zou veel te lang duren.

Mersenne priemgetallen hebben ten opzichte van normale priemgetallen een belangrijke 'bijzondere algebraische' eigenschap waardoor ze veel sneller te vinden zijn dan priemgetallen.

Zie http://mersenne.org/math.htm
onder Lucas Lehmer testing.

Het zoekprogramma dat de LL-test bevat is overigens grotendeels met de hand geschreven in ASM (!), de meest low-level programmeertaal mogelijk, en is waarschijnlijk voor Intel processoren het best geoptimaliseerde programma ter wereld.

Daarom draait het ook iets van 25% langzamer op praktisch alle AMD procs*.

*Zie de benchmarks: http://mersenne.org/bench.htm

[Anoniem: 42145]

de meest low-level programmeertaal mogelijk,

Beetje mierenneuken, maar omdat je het zo stellig brengt: assembly is zeker niet de meest low-level. Heel flauw is machinecode nog 1 level lager (flauw omdat de binaire opcodes 1:1 mappen naar de assembly mnemonic, maar toch een cpu excute geen programma text in character format).

Een stapje lager is direct in de mirco-code van je CPU programmeren. Sommige architecturen staan dit theoretisch toe. Assembly is voor veel systemen vanuit het gezichts punt van de CPU ook maar een high-level taaltje; de zogenaamde ABI.

Binnenin de CPU wordt deze high-level assembly instructie stroom dan omgezet naar de native interne code. Het kan zelfs zijn dat de omzetting relatief zo groot is dat het een andere paradigma wordt. Bekenste voorbeeld is natuurlijk x86.

Zowel de AMD als Intel processoren, alsmede een handjevol andere architecturen hebben de x86 assembly instructies als high-level taal. Toch execute geen van beide CPUs X86 instructies direct. Zelfs binnen de intel familie zijn de netburst interne instructies anders als die van core.

Maar zelf hier kan het NOG lager. Microcode stuurt ook alleen maar je (data) paden binnen je CPU aan. Je kunt ook DIRECT de paden in de gewenste manier instellen voor jouw specifieke probleem. Dit kan 1 malig in hardware (een ASIC), maar kan ook dmv reconfigurable computing systemen.

[Anoniem: 134975]

Valt wel mee hoor!

Testen of een getal een priemgetal is betekent: delen door ieder priemgetal dat kleiner of gelijk is aan de wortel van het te testen getal.

Alle kleinere priemgetallen mogen wel bekend worden verondersteld (zoekalgoritme naar een nieuw priemgetal zal ongetwijfeld oplopende getallen behandelen).

En dus hebben we het over een toch zeer overzichtelijke hoeveelheid benodigde rekenkracht / -tijd.

[.oisyn]

Niet helemaal, dit is een Mersenne priem. Het zoeken naar Mersenne priemen gaat natuurlijk met veel grotere stappen dan de priemgetallen zelf. Zo zou het volgende priemgetal bijvoorbeeld deze priem + 2 kunnen zijn. Maar het algoritme gaat op zoek naar de volgende Mersenne priem, wat 2^q-1 kan zijn, waarbij q het eerstvolgende priemgetal na 32.582.657 is, en dat ligt derhalve minstens een factor 4 verwijderd van de zojuist gevonden priem.

En dan nog het feit dat het algoritme distributed is, waarbij de workload wordt verdeeld over heel veel computers. Niet al die computers gaan dezelfde mogelijke Mersenne priemen testen, ze krijgen allemaal een deel van de zoekruimte.

[Anoniem: 134975]

Wat betreft het 1e deel van je betoog heb je gelijk. Bedacht ik me zelf ook net na mijn post, maar toen riep de plicht van de arbeid en kon ik het niet meer aanpassen. Vraag is dus hoever ze al zijn met het zoeken naar alle mogelijk priemgetallen (geen idee).

Je 2e argument (distributed computing) gaat minder op. zie linkje in de 1e regel van het artikel. In 2003 is via hetzelfde project al een Mersenne priemgetal gevonden dat vele malen groter is dan de wortel van het nu gevonden getal. Lijkt me niet dat ze stukjes meer dan 3 jaar open laten staan. Komt het binnen, zeg, een paar maanden niet terug, dan wijzen ze het wel weer toe aan een ander.

[Poekie McPurrr]

Door middel van distributed computing creer je in feite een supercomputer die de taak aankan. Hoe meer mensen er met hun pc meedoen, hoe krachtiger het geheel word.

[Repsaj_Nav]

Vraagje:
kan je niet "makkelijk" het priemgetal van 10 miljoen cijfers maken door (2^<net ontdekt priemgetal>)-1 te doen?

/// als dit zo is en jullie willen het zo, wil ik wel een deel van die 100.000 hè ;-)

[Sebas1979]

nee, een Mersenne priemgetal heeft wel de vorm 2^priemgetal -1, maar niet alle getallen van de vorm 2^priem - 1 zijn zelf priemgetallen.
Was dit wel zo, dan was het hele project van de Missouri universiteit overbodig geweest.

[StefSybo]

Een Mersenne-priemgetal is inderdaad van de vorm 2^p-1, waarbij p zelf een priemgetal is, maar je kan niet elk willekeurig priemgetal op de plaats van p invullen en er dan vanuit gaan dat dat getal ook priem is.

Kijk maar naar dit getal, dit is pas het 44e Mersenne-priemgetal, terwijl 32.582.657 niet het 44e priemgetal is.

[airell]

Het lijkt volkomen nutteloos, maar de wereld draait om priemgetallen. Volgens mij is (internet) security daar het grootste voorbeeld van! Ga zo door!

[Adion]

Het zou me verbazen als er ook maar 1 security-toepassing is die gebruik maakt van priemgetallen van 10 miljoen cijfers lang.
Ik vrees dat hiermee rekenen zelfs met huidige pc's nog behoorlijk traag zal zijn.

[amdboy]

Waarom zou het je verbazen een priemgetal van 10 miljoen kan jij niet zo snel omrekenen met de huidige pc maar de pc's die daar toegang tot hebben weten het antwoord dus geen zware reken som

http://nl.wikipedia.org/w...vragen_over_priemgetallen

[Anoniem: 77640]

@knirfie: Je kan stoppen wanneer er geen overflow bit meer is. En dat gebeurt met 1/2 kans in de eerste bit, met 1/4 kans in de tweede bit, met 1/8 kans in de derde bit, enz. Een 64-bit processor doet er dus amper ooit meer dan één klokcyclus over.

Zo zijn er nog wel trucken genoeg om snel te werken met grote getallen.

[Vaan Banaan]

Een miljoen clock cycles is niet zoveel hoor. Dat kan een oude C64 zelfs nog in 1 seconde (1 MHz, 8 bits welliswaar) Een redelijk moderne PC stampt die er dus in minder dan een milliseconde doorheen.
Goed, voor computerbegrippen nog steeds traag, maar ik kan niet eens zo snel met mijn ogen knipperen.

[Theo]

Heel simpel gezegd (en natuurlijk in de praktijk niet waar) zou een 32bit processor 1 miljoen clockcycles nodig hebben voor een simpele +1 functie...

1 miljoen clockcycles is voor een beetje pc ook maar een halve miliseconde, dus een beetej pc zou best makkelijk kunnen rekenen met dit soort getallen, en 2.000 berekeingen per seconde noem ik wel fatsoenlijk werken, helemaal met getallen van bijna 10 megebyte groot!

[OpenMinded]

het gaat niet om de grootte van 1 getal ,maar om de tijd die nodig is om alle combinaties na te lopen, zo is de sleutel te kraken.

[knirfie244]

Sorry, maar geen enkele computer kan hier fatsoenlijk mee werken binnen afzienbare tijd.

10 mildoen getallen = 32Mbit!!! (zoals de beschrijving 2^32,582,657-1 ook al aan geeft)

Heel simpel gezegd (en natuurlijk in de praktijk niet waar) zou een 32bit processor 1 miljoen clockcycles nodig hebben voor een simpele +1 functie...

[dasiro]

Heel simpel gezegd (en natuurlijk in de praktijk niet waar) zou een 32bit processor 1 miljoen clockcycles nodig hebben voor een simpele +1 functie...

ofte 1Mhz

[Anoniem: 133254]

Nee hoor, de algebraische getaltheorie is wel degelijk geinteresseerd. "Grootste" priemgetallen zijn natuurlijk maar spielerei, de rest van het veld is wel serieus. En cryptografie is inderdaad een (vanuit wiskundig oogpunt niet zo belangwekkende) toepassing.

<edit> zie ook het gelinkte artikel of zie Mathworld:
de interesse is vooral toegepast wiskundig: een extreem efficient zoekalgorithme. Merk ook dat zowel dit als het vorige priemgetal (gevonden kerstdag 2005) staan er nog met een ? aangeduid: dubbelchecken van alle getallen kleiner dan deze getallen is nog niet gebeurd.
</edit>

[mister X630]

hmmm...

als ik oneindig veel keer '13' of '17' (bijvoorbeeld) achter elkaar blijf plakken dan heb ik toch ook een oneindig groot priemgetal?

edit: ik = (zat effe een beetje (zachtjes uitgedrukt) dom te denken...)

[Mr. B.]

als ik oneindig veel keer '13' of '17' (bijvoorbeeld) achter elkaar blijf plakken dan heb ik toch ook een oneindig groot priemgetal?

Niet bepaald... 131313 is namelijk al deelbaar door 3 (1 + 3 + 1 + 3 + 1 + 3 = 12)

Edit: en wat BarôZZa hieronder zegt is nog makkelijker

[BarôZZa]

1313/13=101
1717/17=101

[DJ Henk]

Niet echt, het is vrij snel te zien dat bijvoorbeeld 131313 geen priemgetal is.

[edit] Hmm.. nu snap ik waarom ik altijd maar een mager zesje had voor wiskunde. Veel te langzaam..

[Anoniem: 170230]

edit: te laat

[beefstick]

onzin: 1313 = 101 * 13 en dus niet priem.

Waarom lees ik die andere replies niet in de hoofd tread

[Anoniem: 168428]

Veel encryptietechnieken zijn er op gebaseerd dat het heel eenvoudig is om een berekening uit te voeren van 2 zeer grote priemgetallen, maar dat het bijna onmogelijk is om het omgekeerde te doen als je alleen de uitkomst hebt. Stel p en q zijn twee grote priemgetallen dan is het gemakkelijk om m=p*q uit te rekenen, maar zo goed als onmogelijk om p en q uit te rekenen als je alleen m hebt. http://nl.wikipedia.org/wiki/Asymmetrische_encryptie

[Anoniem: 171084]

het vierenveertigste Mersenne-priemgetal

Als er maar 44 Mersenne-priemgetallen bekend zijn, lijkt het me nooit veel moeite om p*q terug te vinden... Tenzij ze ook n iet-Mersenne-priemgetallen gebruiken, maar dat maakt de Mersenne-priemgetallen meteen waardeloos en niets bijzonders.

[Vaan Banaan]

Niet helemaal, ze worden nog gebruikt voor random generatoren. http://nl.wikipedia.org/wiki/Mersenne-twister

[Anoniem: 54081]

Mja, toch ff natellen dit...

[Anoniem: 188613]

Iemand al de faculteit van het getal in MS Calc ingevoerd en uitgerekend?

[gfgw]

... omdat ze niet alleen deelbaar zijn door zichzelf en door 1 ...

En ik maar denken dat de definitie van een priemgetal is: ieder geheel getal dat precies twee delers heeft. Volgens deze definitie is 1 geen priemgetal, volgens bovenstaande quote wel.