Cookies op Tweakers

Tweakers maakt gebruik van cookies, onder andere om de website te analyseren, het gebruiksgemak te vergroten en advertenties te tonen. Door gebruik te maken van deze website, of door op 'Ga verder' te klikken, geef je toestemming voor het gebruik van cookies. Wil je meer informatie over cookies en hoe ze worden gebruikt, bekijk dan ons cookiebeleid.

Meer informatie

Onderzoekers ontdekken priemgetallen met meer dan tien miljoen cijfers

Onderzoekers hebben bekendgemaakt dat er twee nieuwe Mersenne-priemgetallen zijn ontdekt: 243.112.609-1 en 237.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 2p-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 232.582.657-1. Twee jaar lang was het rustig op het Mersenne-priemgetalfront, maar op 23 augustus van dit jaar werd het getal 243.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 237.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.

Door Harm Hilvers

Freelance nieuwsposter

17-09-2008 • 11:27

134 Linkedin Google+

Submitter: Onbekend

Reacties (134)

Wijzig sortering
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 2p-1. Er kan een laatste Mersenne Priemgetal zijn, in welk geval alle hogere priemgetallen een andere vorm hebben.
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.
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 2p-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.
( 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 17 september 2008 14:48]

Er zijn niet zoveel Mersenne priemgetallen bekend. Ook geldt niet voor alle priemgetallen P dat 2P-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.
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.
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.
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)
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?

Op dit item kan niet meer gereageerd worden.


OnePlus 7 Pro (8GB intern) Microsoft Xbox One S All-Digital Edition LG OLED C9 Google Pixel 3a XL FIFA 19 Samsung Galaxy S10 Sony PlayStation 5 E3 2019

Tweakers vormt samen met Tweakers Elect, Hardware.Info, Autotrack, Nationale Vacaturebank, Intermediair en Independer de Persgroep Online Services B.V.
Alle rechten voorbehouden © 1998 - 2019 Hosting door True