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.
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.
( 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]

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.
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?
Priemgetallen zijn super belangrijk bij het encrypten van gegevens, denk aan SHA1. Hoe groter het priemgetal, des te moeilijker te kraken!
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 17 september 2008 11:58]

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.
Volgens mij is de initialization vector van MD5 simpelweg waarden uit de sin() functie. Priemgetallen hierin zouden toeval zijn en geen functie dienen.
Laat sinus (een reeksontwikkeling 'functie') nou juist gebruikt kunnen worden om priemgetallen uit te rekenen (zie formule). :Y) :+

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.
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 !
Tja, das nogal logisch als je ze in de vorm van (2^x)-1 kan schrijven.
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.
omdat wanneer je ze makkelijk kan berekenen, ze niet meer bruikbaar zijn.
Men weet dat er grotere (abstract) priemgetallen zijn, niet welke getallen (exact) hier nog meer onder vallen.
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.
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?
... 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 ;)
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 17 september 2008 11:38]

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 2n - 1 hebben. 5 is bijvoorbeeld wel een priemgetal, maar geen Mersenne-priemgetal.

[Reactie gewijzigd door ATS op 17 september 2008 11:50]

"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 2P - 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:

23 - 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.
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.
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 17 september 2008 11:34]

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.
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 17 september 2008 13:14]

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 17 september 2008 11:52]

Op dit item kan niet meer gereageerd worden.


Apple iPhone 11 Nintendo Switch Lite LG OLED C9 Google Pixel 4 FIFA 20 Samsung Galaxy S10 Sony PlayStation 5 Auto

'14 '15 '16 '17 2018

Tweakers vormt samen met Hardware Info, AutoTrack, Gaspedaal.nl, Nationale Vacaturebank, Intermediair en Independer DPG Online Services B.V.
Alle rechten voorbehouden © 1998 - 2019 Hosting door True