Grootste priemgetal ooit gevonden

De New Scientist meldt dat het rijk der priemgetallen er een groot broertje bijgekregen heeft. Michael Shafer, een 26 jaar oude student uit Michigan in de VS ontdekte het grootste priemgetal, dat bestaat uit liefst 6.320.430 cijfers. Zijn computer, die de eigenlijke ontdekker van het priemgetal is, maakte deel uit van het Great Internet Mersenne Prime Search-project, dat met de hulp van meer dan 60.000 vrijwilligers op zoek gaat naar nieuwe priemgetallen. Die vrijwilligers bestaan niet enkel uit mensen geïnteresseerd in wiskunde, maar ook uit mensen die de prestatie en stabiliteit van hun systeem willen testen. Wie als eerste een priemgetal met meer dan tien miljoen cijfers vindt maakt aanspraak op de hoofdprijs van 100.000 dollar.

"I had just finished a meeting with my advisor when I saw the computer had found the new prime," Shafer says. "After a short victory dance, I called up my wife and friends involved with GIMPS to share the great news."

Prime numbers are positive integers that can only be divided by themselves and one. Mersenne primes are an especially rare type of prime that take the form 2^p-1, where p is also a prime number. The new number can be represented as 2^20,996,011-1. It is only the 40th Mersenne prime to have ever been found.

Reacties (143)

[FendtVario]

Ik heb hier nog een pc met linux dual p3 800 en 1,5gb geheugen. Die zullen we ook eens aan het werk zetten

Wie als eerste een priemgetal met meer dan tien miljoen cijfers vindt maakt aanspraak op de hoofdprijs van 100.000 dollar.

Waarom beginnen ze dan niet gewoon met rekenen bij
1 * 10^10.000.000 (klopt het zo??)

[Kheldar]

Volgens mij is het idee dat als je een getal niet kan delen door alle priemgetallen voor dat getal, dat het dan een priemgetal is (alle andere getallen zijn namelijk meervouden van een van die priemgetallen).

Als je dus nu alvast bij de getallen van 10 miljoen cijfers begint, mis je er dus nog een aantal (als je nu vast begint kun je al wel vast een voorsprong opbouwen ).

[eggieman]

Dat klopt.
Maar Mersenne Priemgetallen zijn een apart soort. Vroeger dacht men dat 2^(een priemgetal)-1 ook een priemgetal was. Deze worden Mersenne Priemgetallen genoemd. Meer uitleg staat wel op de site http://primes.utm.edu/mersenne/index.html.
En voor iedereen die een beetje getalletjes gek is (net als ik) http://primes.utm.edu/ vertelt werkelijk alles over priemgetallen.

Deze priemgetallen kun je makkelijker controleren, een uitleg staat ook op de site. (Moet je wel iets weten van wiskunde) Anders moet je te veel getallen door lopen.
10^10.000.000 controleren tot aan de wortel 10^5.000.000 laat 1 op de 1000 (een schatting)priem zijn krijg je een lijst van 10^4.999.997 getallen die moet door lopen. Laat hem elke kloktik er 1 controleren (dat haalt hij compleet niet) op 3Ghz zijn dat 3*10^9 * 3600 = 10^13 berekeningen per uur dus
10^4.999.984 uur...
Dat zijn er echt te veel voor je leventje.

[SimiusMagnus]

Ik geloof dat er bepaalde methoden bestaan om te testen of een getal met een zekere kans een priemgetal is.

[Anoniem: 89475]

Weet niet wat je er mee bedoeld, maar in ieder geval is 1*10^10.000.000 gewoon een 1 met 10 milj. nullen, ben je dus toch nog nergens...

[Anoniem: 52621]

Dan zulen de meesten nu ook wel gaan doen nu...

[Anoniem: 89475]

Wie test dat getal??????? Een computer natuurlijk, maar hoe? Dat gaat lang duren.

[off topic maar bizar] Als je het getal op moet schrijven, stel je neemt 3 mm per cijfer, maal 6.320.430, is een cijfer van 19 km!! En als je zeg 1 sec over 4 cijfers doet, ben je ruim 18 dagen bezig!!

[YopY]

Heb je ook een goede rekenmachine? wat is 2220,996,011-1 voluit? (zie artikel voor juiste formulering, hier is geen superscript mogelijk, geloof ik)

[eggieman]

Nu in die tijd is je Atlon op 2000 Mhz net halverwege met controleren, dus met dat jij hem 2x op schrijft istie klaar. (of als je nog keer een uurtje wil slapen)

[Anoniem: 21507]

De organisator van het GIMPS project, George Woltman, heeft de beschikking over een Cray (waarschijnlijk op z'n werk) om het na te rekenen. Dat duurde daar meende ik een dag of 2.

[Nyarlathotep]

Waar kan ik dat programma downloaden?? Goeie stress-test voor mijn pc...

edit: Ha, bedoeld als grap, kun je het nog werkelijk vinden ook... Vraag me alleen af hoelang een standaard thuis-pc erover doet om die grote getallen te berekenen...

[wh-vanderpost]

Even het artikel bekijken.. en gij zult vinden.

http://www.mersenne.org/

[glashio]

Gaat DPC zich hier mee bezig houden ?
Zijn er dagelijkse stats ?
* 786562 glashio

[Anoniem: 14038]

Nou ja, als SETI voorbij is gaan de natuurlijk metteen over op het hacken van die buitenaardse netwerken. Dat moet ook gebeuren.

[Kurgan]

Ja kijk maar naar Independence Day. Is meteen bewezen dat hackers wel degelijk goeie dingen kunnen doen.

[Anoniem: 65371]

Je kan dat programma van de volgende link downloaden:

http://www.mersenne.org/freesoft.htm

Heb het programma ook al geinstalleerd, er valt immers veel geld te winnen

[edit]Hmm, wh-vanderpost was me te snel af[edit]

[Anoniem: 62211]

ik denk dat het uitreken van een getal niet moeilijk is (iedere vermenigvuldiging van 2 is gewoon een bitshift naar links) maar uitrekenen of het een priemgetal is (delen door 2, door 3 tm de helft van zichzelf) en kijken of er een geheel getal uitkomt... da's een stukje intensiever

[Fulcrum2000]

tm de wortel van zichzelf

En getallen met als laatste cijfer een 0,2,4,5,6 of 8 kun je direct overslaan.

[FailFr8er]

Omdat je 2000 kan delen door 2? (en door veel meer getallen...)

[Anoniem: 18254]

Zo zo Edwin G, dus volgens jou is 9 een priemgetal?

[EdwinG]

(ok, had ik er nog bij moeten zetten)
Als de wortel een geheel getal is (en 3 lijkt mij een heel getal) is het geen priemgetal (is immers te delen door een heel getal)

[EdwinG]

Volgens mij hoef je het alleen te proberen met priemgetallen die kleiner zijn dan, de wortel, scheelt een hoop werk.

[Fulcrum2000]

@EdwinG Huh? Hoe ga je dan aantonen dat 2000 geen priemgetal is?

[jvo]

Er is een algoritme dat berekent of een getal een priemgetal is en in O(log^6 n) loopt. Heeft volgens mij op tweakers gestaan.

[Anoniem: 86857]

Het originele PRIMES is in P algoritme (AKS) komt uit 1992 en heeft complexity O(log^7.5 n). Het toen gevonden algoritme was een flinke doorbraak en sindsdien is men weer lekker bezig betere varianten te vinden. Het algoritme zelf heeft echter weinig tot geen invloed gehad op bijvoorbeeld cryptography doordat de priemtest maar een onderdeel is van het RSA algoritme (of het kraken ervan).

In 2003 heeft ene Bernstein een variant gevonden met complexity (lg n)^(4+o(1))

Berrizbeitia [Berrizbeitia2003] found a way to save time in AKS-type primality proofs for some primes n, reducing the exponent from 6+o(1) to 4+o(1). Cheng [Cheng2003] extended Berrizbeitia's idea to more primes n, and Bernstein [Bernstein2003] extended it to all primes n. The algorithm for finding these proofs relies on some randomness, unlike the original AKS algorithm.

It seems plausible that a variant of AKS may soon compete in practice with ECPP for 'general' primality proofs. This field is in great deal of flux at this time!

Zwaar interessant maar voorlopig nog van weinig nut.

[kris_112]

Er zijn snellere manieren om te controleren of een getal een priemgetal is. Het nadeel hiervan is alleen dat je hiermee alleen met "aan zekerheid grensende waarschijnlijkheid" kunt zeggen of een getal priem is of niet.

Deze berekening vertelt of een getal niet een priemgetal is, maar er is een kans van 50% dat het geen priemgetal is maar toch door de test komt. Als deze berekening een groot aantal keer herhaald wordt en steeds weer door de test komt is de kans zeer groot dat het gekozen getal een priemgetal is. Ik meen dat in programma's als PGP op deze manier ook de priemgetallen berekend worden.

[jp]

Heeft dit nog iets te maken met dingen als encryptie, die ook met priemgetallen werken?

(Ben niet zo'n wisknudde held )

[Tootoo]

Jep, dingen als RSA berusten volledig op priemgetallen... Mocht zoiets gekraakt worden, dan gaan er best wat probleempjes ontstaan

Hoe groter een priemgetal ook, des te moeilijker is het om de vercijferde tekst te kraken bij RSA (en neem ook aan bij andere encryptie methodes).

[familyman]

Als je nu een lijstje van deze getallen op je computer hebt, vergemakkelijkt dit dan het kraken van op priemgetallen gebaseerde codes?

[Tootoo]

Voor RSA geldt dus het volgende (heel globaal gezegd):

Neem 2 grote priemgetallen en vermenigvuldig deze met elkaar. Met dit resultaat, samen met de publieke en prive sleutel (ook verkregen dmv de priemgetallen), wordt een tekst versleutelt en ontsleutelt.

Als je RSA wilt kraken moet je iets bedenken om te weten te komen wat die priemgetallen waren. Je weet dan wel de publieke en privesleutel, maar niet het resultaat van de priemgetallen. En dit is dus een enorm rekenintensief proces. Hoe groter de priemgetallen, hoe groter moeilijker te kraken Het wordt namelijk bijna als onmogelijk beschouwd dat er hiervoor een formule is (gevaarlijke stelling wel ). Met andere woorden, het moet op een brute force manier (alle mogelijkheden proberen). En daar doe je zo enorm lang over Zie daarvoor bv wel het RC5 project, dat houdt zich (correct me if i am wrong) zo ongeveer wel mee bezig

Ook al heb je een hele waslijst van priemgetallen, je moet net die 2 hebben, wil je er een beetje sneller achter komen

[kris_112]

Daarom zijn de sleutels bij RSA ook zo belachelijk lang vergeleken met klassieke cryptosystemen; de priemgetallen die genomen worden zijn meestal tussen de 100 en 200 cijfers.
Het aantal priemgetallen totaan een getal x is ongeveer x / ln(x), dus het aantal priemgetallen van 98 (meer paste niet op m'n rekenmachientje ) cijfers is dan ongeveer:
10^99 / ln (10^99) - 10^98 / ln (10^98) = 3,94 * 10^96, dus jouw oplossing zit er helaas niet in.

Volgens een (belachelijk oude, te weten 1985) tabel uit m'n cryptoboek:
# cijfers - factorisatieduur
100 1 jaar
125 100 jaar
150 10.000 jaar
200 30M jaar
225 1G jaar
250 60G jaar

computers zijn in 20 jaar een tikkeltje sneller geworden, maar het geeft in elk geval een aardig idee van hoeveel tijd een brute-force attack kost.

edit:
was bedoeld als reactie op familyman; beter klikken volgende keer

[familyman]

Gegeven dat tussen tussen priemgetallen een hele hoop onbruikbare getallen zitten, is een array priemgetallen dan dus een grote hulp, lijkt me.

Het grote getal bestaat uit twee priemfactoren, die je dan in een lijst kan uitzoeken. Matrixvermenigvuldigen lijkt me dan niet zo'n grote klus. Of werken de kraak-algoritmes grofweg al zo?

Voor de overige sluit ik me aan bij de oproep van Mindbender. Weet er iemand hier iets meer over?

[Anoniem: 92540]

Als ik het goed onthouden heb, is het probleem om van een getal te ontdekken in welke factoren het ontbonden kan worden, een zgn. semi-NP-moeilijk probleem. Dat wil zeggen dat we zeer sterke vermoedens hebben dat het probleem niet in minder dan exponentieel veel tijd opgelost kan worden (exponentieel in de grootte van de input). Een voorbeeld van een exponentiele functie: met input 10 en grondtal 2 krijgen we 2^10 = 1024. Bij veel grotere aantallen, zoals bv. bij het nagaan van alle mogelijke waarden van binaire sleutels van 256 bits lang, hebben we dan al 2^256 waarden = 1.16 × 10^77. De NP-klasse (niet-polynomiaal) wordt dus waarschijnlijk door dergelijke functies beschreven. De klasse P (polynomiaal) kent tijdfuncties die (analoog aan genoemde voorbeelden) veel prettiger uitkomsten hebben: 10^2 of 256^2 ...

Dit is allemaal gericht op de vraag of 'P=NP', oftewel: kunnen NP-problemen stiekem toch in polynomiale tijd opgelost worden? Als iemand dat ooit kan bewijzen, dan stort oa. RSA in.

[edit: veel typo's]

[Anoniem: 55933]

Wel knap als je priemgetallen kraakt
Het is nooit bewezen dat RSA onkraakbaar is, het is wel degelijk kraakbaar, maar de veiligheid van RSA is gebaseerd op de tijd die het zou kosten (op dit moment jaren) om zo'n enorm priemgetal te factoriseren.
Helaas is het public key systeem over het algemeen ook nogal langzaam omdat met zulke grote getallen moet worden gewerkt

[Anoniem: 92540]

Inderdaad; daarom wordt RSA vaak alleen gebruikt om een 3DES-sleutel te coderen; 3DES werkt veel sneller (is erop gericht om hardwarematig ge(de)codeert te worden). Ik vraag mij echter af of 3DES tegenwoordig nog wel veilig is.

Note (nogal technisch, maar wel grappig):
In de praktijk blijken NP-moeilijke problemen soms nog wel mee te vallen. Ik heb zelf gewerkt aan een soortgelijk probleem, en het bleek dat met wat simpele rekenregels heel veel van de 'franje' van een probleem weg te werken viel. Het resterende probleem was dan soms zo klein geworden, dat dit met brute rekenkracht op te lossen was. Het deel van de oplossingsruimte dat voor de exponentiele rekentijd zorgt is dus soms best klein of onrealistisch!

Of dit voor RSA ook geldt, weet ik niet - maar het zou mij niet verbazen. Het is echter een hele kunst om die simpele rekenregels te vinden; je moet hun geldigheid nl. wel bewijzen.

[Anoniem: 75364]

Zie hier voor uitleg:

http://www.lhs.logan.k12.ut.us/~rweeks/applied/secretcode.htm

[Anoniem: 92624]

Wist je dat je een nobel prijs kan winnen als je een formule kan schrijven, die ieder priemgetal kan genereren. Er zit totaal geen logica in priemgetallen. (alleen dat ze niet door een ander rond getal zijn te delen, behalve 1) (hierdoor zijn ze ook nooit 'even' )

1, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41
verschil= +2 + 2+ 2+ +4+2+4+2+4+6+2+6+4

aarghh....

[Sokratesz]

Het mooie van deze priemgetallen is dat ze door geen enkele berekening gefaked kunnen, worden, een priemgetal is immers alleen deelbaar door 1 en zichzelf. Banken gebruiken deze methode om transacties te versleutelen.

Je neemt 2 ontzettend grote priemgetallen, die vermenigvudig je met elkaar. Het getal dat je nu hebt, zal door geen enkele computer weer opgedeeld kunnen worden in die 2 priemgetallen, zodat je de ultieme veilige code hebt. (het kan wel, maar daar zijn honderden jaren voor nodig, zeker als je nagaat dat het om twee getallen gaat met meer dan 100.000 cijfers elk)

De bank verstuurd de sleutel met de transactie, en alleen diegene met de twee priemgetallen kan het bericht ontcijferen, anders is het onmogelijk.

(bron: KIJK, maand december)

edit:


De banken hebben een vaste lijst met priemgetallen, die per uur wisselen. Daar is speciale software voor, zodat een bericht verstuurd om 14:35 een andere encryptie heeft dan een bericht verstuurd om 15:35. Het geheimhouden van een lijst met priemgetallen is makkelijker dan het geheimhouden van een vaste code die je elke keer gebruikt. (zoals de duitsers deden in de 2e wereldoorlog, eenmaal gekraakt, altijd
gekraakt)

[Anoniem: 52621]

Precies.

Dan zou het dus alleen een kwestie zijn om met een lijst grote priemgetallen te rekenen om zo de encryptie te kraken.

Veiliger lijkt mij om wat minder grote priemetallen te nemen, ergens in de middenrange, laten we zeggen met 3 miljoen cijfers achter de komma.. Lijkt me dan toch een stuk veiliger :-)

En waarom niet meer priemgetallen vermenigvuldigen? 3? of 10?

[Anoniem: 83450]

Veiliger lijkt mij om wat minder grote priemetallen te nemen, ergens in de middenrange, laten we zeggen met 3 miljoen cijfers achter de komma.. Lijkt me dan toch een stuk veiliger :-)

Priemgetallen zijn per definitie hele getallen.

Anders is 3 ook geen priemgetal, is immers deelbaar door 1, 3 en 1.5

---

Daarnaast. Wat is het verschil tussen een getal met 3 miljoen cijfers achter of voor de komma?


-----

Laatste. Snap zelf niet helemaal waarom je priemgetallen nodig hebt. Is wel leuk dat priemgetal1 * priemgetal2 een groot getal oplevert, maar dacht dat je minimaal voor decryptie het grote getal en een van de priemgetallen gebruikt. In dat geval maakt het niet uit of je een product van twee priemgetallen gebruikt of niet. Zie het al. Tijd om wat linkjes te gaan lezen.

[mjl]

Ja en om 't te kraken neem je dus gewoon een lijst met de bekende priemgetallen die je met elkaar vermenigvuldigd totdat je je antwoorde hebt en voila daar heb je je sleutel, het zal dus wel iets moeilijker gaan dan dit.

[n4m3l355]

het kleine verschil is dat enigma wel te kraken is via een standaard algoritme (en dus een logica bevat) binnen de 10 seconde terwijl 2 grote priemgetallen "kraken" wel wat langer duurt

[D-RiSe]

ik heb eigenlijk nooit begrepen waarom 2 niet een priemgetal is

de reden dat een priemgetal nooit even is komt omdat ie dan altijd door 2 te delen is... maar in het geval van 2 maakt dat niet uit omdat ie zelf 2 is....

dus.. kan iemand me uitleggen waarom 2 geen priemgetal is?

[RobT]

2 is wel een priemgetal.

[mangosap]

En 1 is geen priemgetal...

http://www.utm.edu/research/primes/notes/faq/one.html

[pietje63]

Als ik me niet vergis is 2 wel een priemgetal... Helaas heb ik mijn analysis boeken niet hier liggen daar staat nog heel wat (te veel vond ik vorig jaar) theorie over priemgetallen.

Om verder nog even terug te komen op het systeem om priemgetallen als encryptie te gebruiken:

bank 1 heeft een data pakket en versleuteld dat met priemgetal A en stuurt verder de sleutel C, zijnde A*B mee.

bank 2 ontvangt het data pakket en heeft priemgetal B; deelt C door B en heeft daardoor priemgetal A waardoor het data pakket ontsleuteld kan worden.

Als je niet beschikt over het priemgetal B is het heel moeilijk om priemgetal A te achterhalen en dus het pakket te ontsleutelen.

[Anoniem: 50681]

wist je dat er geen nobelprijs voor wiskunde is? (en je DUS nooit de nobelprijs voor het vinden van een priemformule sec zult winnen...)

[DarkX]

Ach, je kunt wel de Field's Medal winnen, die heeft ong de status van de nobelprijs binnen de wiskunde.

Ik denk trouwens dat het vinden van het volgende grote priemgetal an sich niet zo ver weg hoeft te liggen, het volgende Mersene priemgetal is natuurlijk een heel ander verhaal Dat maakt dit getal natuurlijk toch net iets meer bijzonder, aangezien er nu 40 Mersene priemgetallen zijn en eh... HEEL VEEL gewone priemgetallen

[Anoniem: 98134]

Omdat ie onder wetenschap valt.

[Anoniem: 52621]

die formule is niet te schrijven, want die formule zou oneindig lang zijn.

Ik zou wel een formule kunnen schrijven die elk priemgetal van 1 tot 10 miljoen zou kunnen vinden...
Maar die formule zou langer zijn dan de priemgetal zelf. dus laat maar :-)

[jfk]

Er zit totaal geen logica in priemgetallen. (alleen dat ze niet door een ander rond getal zijn te delen, behalve 1) (hierdoor zijn ze ook nooit 'even' )

Euhm, niet helemaal... Er is om precies te zijn een (1) even priemgetal. Het zit tussen 1 en 3. Raad eens? Juist!

[Anoniem: 95952]

reactie @ omixium

geef mij maar dan een nobelprijs

check:
0+0+1 = 1
1+1+1= 3
2+2+1= 5
3+3+1= 7
4+4+1= 9
5+5+1= 11
6+6+1= 13
etc, das dus eigenlijk niet moeilijk om een priemgetal te maken
dus om boven de 10 miljoen cijferige priemgetal uit de komen
gebruik het getal wa in de topic staat
priemgetal + priemgetal +1 en je hebt een nieuwe

[Hielko]

Ja. en 7+7+1 = 15

15/3=5=dus geen priem

[Foeth]

4+4+1=9 een priemgetal? Zo simpel is het dus echt niet.

"priemgetal + priemgetal +1 en je hebt een nieuwe"

13+13+1=27?

[siren]

@ celticfist En doe eens 7+7+1 en deel dat door 3 of 5?
en foeth deel 27 eens door 3?

[Foeth]

@ Siren

He, je hebt 'm door

[Hakker]

7+7+1=15 en die gaat dus niet Dag nobelprijs
Goh en ik ben de zoveelste die ermee komt

[pietje63]

7+7+1 = 15
dag theorie

edit:
ik moet voortaan refreshen voor het reageren

[Anoniem: 82810]

[edit: never mind....]

[Anoniem: 71268]

9 is dus geen priemgetal

edit:
goed ik was dus echt te laat :

[Anoniem: 55241]

7+7+1=15 need to say more

edit : Oeps major dubbelpost

[Eegee]

Hee, wat doet de 9 daar in het rijtje?
Aargh, waarom zag ik die superdubbelposts niet? Hmm niveau stond niet goed. Sorry...

[Anoniem: 4697]

Het enige nadeel is dat er geen Nobelprijs voor de wiskunde is...

[Anoniem: 58450]

Je kunt op je vingers natellen dat er wel weer een grotere gevonden zal worden!

<edit> Maar ff serieus: ik heb eigenlijk nooit goed begrepen waarvoor het vinden van priemgetallen nou nuttig is. Kun je het nog ergens voor gebruiken anders dan voor een leuke stress-test?</edit>

[Arjan A]

Het vinden van priemgetallen is ook nuttig voor encryptie. Daar heb je priemgetallen nodig voor de encryptiesleutels. Hoe het precies werkt weet ik ook niet .

Overigens vind ik de term "grootste priemgetal ooit" een beetje pretentieus; er zijn altijd grotere. Ze zijn alleen nog niet gevonden.

[Anoniem: 34437]

hm is het niet bewezen dat priemgetallen niet oneindig groot kunnen zijn?

ben niet zeker dat het reeds bewezen is, maar het wordt iig toch aangenomen

[eggieman]

Dit is NIET waar, het bewijs is anders. Eerst het juiste bewijs dan een voorbeeld.

Het juiste bewijs.
Stel er zijn n priemgetallen die we
p1 tot pn noemen.
als we deze allen vermenigvuldigen krijgen we een getal. Als wij hier er 1 bij tellen krijgen we een nieuwgetal die niet deelbaar is door 1 van bovenstaande getallen, immers delen door p1 levert een rest 1 en zo bij alle anderen ook.
Conclusie hieruit :
OF dit getal is nergens deelbaar door en dus een priemgetal (dus de aanname dat er maar n priemgetallen is fout, bewijs uit het ongerijmde)
OF dit getal is deelbaar door een andere getallen die geen delers hebben in p1 tot pn dus andere grotere priemgetallen.

Bewijs dat jouw idee fout is :

de reeks 2* 3* 5* 7* 11* 13 = 30030 dit plus 1 wordt
30031 en die is deelbaar door 59 (priem) en 509 (priem) en beide groter dan 13

[SimiusMagnus]

Ik dacht juist dat het bewezen was dat er geen grootste priemgetal bestond, en dat ze dus wel oneindig groot kunnen worden.

[Anoniem: 47180]

Als je een tamelijk groot priemgetal neemt, je vermenigvuldigt dat met alle priemgetallen die kleiner zijn en je telt er 1 bij op, dan is de uitkomst weer een priemgetal. Zo kan er dus nooit een grootste priemgetal bestaan.
Een voorbeeld in het klein:
Stel het grootste priemgetal dat je kent is 13.
13 * 11 * 7 * 5 * 3 * 2 = 30,030 (zegt mijn rekenmachine)
30,031 is dan weer een priemgetal... Hmm sorry, zo is het niet eens erg verhelderend, omdat het alweer zo'n groot getal is. Maar je kan wel makkelijk nagaan dat het door geen van de ons "bekende" priemgetallen 2,3,5,7,11 en 13 deelbaar is.
Met wat meer moeite kan je dus aantonen dat dit altijd het geval is en niet alleen in speciale gevallen.

[Anoniem: 3501]

Het is bewezen dat er oneindig veel verschillende priemgetallen bestaan.

Zie bijvoorbeeld: http://mathforum.org/isaac/problems/prime1.html

Ook geldt dat het aantal priemgetallen kleiner dan een willekeurig gegeven priemgetal eindig is.

Bewijs dat er geen grootste priemgetal bestaat: (volgt ook al direct uit het constructieve bewijs onder de link)

Dus bestaat er geen grootste priemgetal want dat zou betekenen dat er eindig veel priemgetallen zouden zijn. Immers het aantal priemgetallen kleiner dan dit getal is eindig en het was aangenomen dat er geen grotere priemgetallen bestaan.

[Rapzar]

@eenmadcat:
Omdat je het product van alle priemgetallen + 1 moet nemen. Als 7 de grootste is die je kent kun je niet:
stap1: (5x3x2)+1=31
stap2: (31x5x3x2)+1=931 want 931=7x7x19 dus geen priem

je weet niet welke priemen er nog tussen liggen

[Madcat]

ik zou het bijna geloven.
7,31 zijn inderdaad priemgetallen en 211 zou dat ook nog wel eens kunnen zijn

maar waarom kan er dan niet snel een groot priem getal berekend worden?
als je dit recursief zou oplossen dan heb je al snel een groot priem getal.

edit:
@rapzar
hmmz ja, maar stel dat je dus alle getallen tussen 1 en 6.320.430 cijfers hebt, dan is de kans wel erg groot dat je als je die getallen als verzameling neemt. een correct getal hebt van boven de 10M cijfers.

maar er zullen denk ik wel gaten in ziten ja.
maargoed wie zegt dat ze al die getallen hebben...

[Madcat]

kijk, dank je... die 59 zag ik niet!

ik dacht al.. dit is te mooi om waar te zijn. andes zouden priem getallen veel sneller ontdekt kunnen worden.

[QuarK]

Dat is absolute @Onzin die je nu verkoopt.
Om je stelling maar gelijk te weerleggen:

509 x 59 = 30031

Er is op dit moment geen foolproof methode om priemgetallen te genereren.
Kom met een werkende methode en je bent in 1 klap wereldberoemd

edit:
Sorry, dacht dat nog niemand em verbeterd had, de layout staat niet zoveel geneste reacties toe..
Helemaal mijn fout.

[Anoniem: 98963]

Integendeel, het is (al meer dan tweeduizend jaar geleden door de oude Grieken) bewezen dat er priemgetallen van willekeurige grootte bestaan (en dat is zelfs heel simpel: neem het produkt van alle bekende priemgetallen, tel daar 1 bij op, dan heb je een nieuw (en groter) priemgetal). Strikt genomen heb je trouwens gelijk dat er geen priemgetallen met oneindig veel decimalen bestaan want zo'n getal zou ook oneindig groot zijn en dat kan niet voor een natuurlijk getal.

Oeps beetje laat. Eerst verder lezen voortaan...

[MindBender]

Ik geloof dat priemgetallen bij encryptie gebruikte worden om een public key te genereren door twee priemgetallen (die samen de private key vormen) met elkaar te vermenigvuldigen. Het vergt namelijk erg veel rekenkracht om uit te zoeken uit welke twee priemgetallen de public key bestaat.

Kan hier iemand wat verdere uitleg over geven (aub)? Erg interessant namelijk.

Verder kun je door priemgetallen te gebruiken gemakkelijk hoofdrekenen met grote getallen. Delingen doe je door de getallen eerst te ontbinden in priemgetallen en die vervolgens tegen elkaar weg te strepen.

Weet iemand hier meer over? Ik herinner me dat er leuke truukjes mogelijk waren.

[Anoniem: 17238]

De werking van RSA encryptie staat in taal voor gewone mensen hier beschreven: http://www.utexas.edu/lbj/21cp/syllabus/whatisakey.htm

En zie ook:

http://world.std.com/~franl/crypto/rsa-guts.html

[Tootoo]

Ik geloof dat priemgetallen bij encryptie gebruikte worden om een public key te genereren door twee priemgetallen (die samen de private key vormen) met elkaar te vermenigvuldigen. Het vergt namelijk erg veel rekenkracht om uit te zoeken uit welke twee priemgetallen de public key bestaat.

Kan hier iemand wat verdere uitleg over geven (aub)? Erg interessant namelijk.

Als je een beetje wiskunde hebt gehad dan snap je het volgende wel (dit zal ook wel te vinden zijn in de links van KuRMiE). Het nemen van de public key gebeurd als volgt:

1) Neem 2 priemgetallen, p en q (in de grote van een paar 100 cijfers).
2) Bepaal het product van p en q: dat heet n (wordt gebruikt bij het versleutelen van de tekst).
3) Bepaal K door (p-1).(q-1)
4) Neem een random getal e, waarvoor geldt dat de grootste gemene deler van K en e 1 is (heet relatief priem).

Het getallenpaar {e,n} is nu je publieke sleutel.

5) Bereken het getal d, zodanig dat ed = 1(mod K).

Het getallenpaar {d,n} is nu je privesleutel.

Mensen weten de publieke sleutel. Of te wel ze weten e en ze weten n. Maar niet K en natuurlijk d ook niet. Het uitrekenen van deze 2 is dus iets wat zoveel rekenkracht kost. Je wilt erachter komen wat K nu is, maar daar kom je alleen achter als je p en q weet. En het ontbinden in priemfactoren.... daar kun je heel wat rekenkracht voor gebruiken. Er is maar 1 combinatie mogelijk Met een simpel programmatje als derive kun je zoiets uittesten. Geef een getal op wat het prorgamma moet ontbinden in priemfactoren: doe dit met 20 cijfers en je pc staat al een lange tijd te ratelen

[mvds]

Verder kun je door priemgetallen te gebruiken gemakkelijk hoofdrekenen met grote getallen

Vraag me alleen af hoeveel makkelijker het zal worden als je gaat hoofdrekenen met een priemgetal van 6 miljoen cijfers

[Rapzar]

Er is ook geen absoluut grootste priemgetal. Er is niet zo lang geleden aangetoond dat tussen een priemgetal en zijn dubbele altijd nog minimaal 1 priem ligt. ergo:er komt nooit een eind aan de reeks

[familyman]

ik heb geen wiskundeknobbel. maar volgens mij was al lang bewezen dat de reëele getallen oneindig zijn. Omdat priemgetallen daar een subset van zijn, lijkt het me zonder 20 pagina's bewijs evident dat er oneindig veel zijn.

Het grote nut zit hem geloof ik alleen in het zijn van een onderdeel in het opstellen, niet kraken van sleutels en voor die mannen die getrouwd zijn met vrouwen die kicken op de MFLOPS van hun man? (Of MIOPS in dit geval...)

Weet iemand verder nog een nut? Als pariteitscontrole bij quantumdots of zoiets meer exotisch?

[Rapzar]

al lang bewezen dat de reëele getallen oneindig zijn. Omdat priemgetallen daar een subset van zijn, ...evident dat er oneindig veel zijn.

Hoezo evident. 'alle getallen kleiner als 10' is ook een subset van de reeele getallen, maar toch echt wel eindig groot (9 elementen)

[Anoniem: 37013]

Overigens vind ik de term "grootste priemgetal ooit" een beetje pretentieus; er zijn altijd grotere. Ze zijn alleen nog niet gevonden.

Hij bedoelt het grootste priemgetal dat tot nu toe gevonden is, niet het grootste priemgetal dat er bestaat .

[Biermeester]

Het grootste priemgetal dat ooit gevonden is.
[Damn....DP :(]

[enchion]

Dan ben je wel even aan het tellen

[Z-Dragon]

Probeer jij eerst maar eens om 6.320.430 op je vingers te tellen.

[Anoniem: 52621]

en volgende maand in het nieuws:
Foutje.. getal bleek na lang onderzoek TOCH deelbaar te zijn...

door 10.

[Qwerty-273]

Het getal is door twee verschillende programma's getest, dit om eventuele programmeer fouten op te vangen. Beide programma's voeren een Lucas-Lehmer test uit. Prime95 is geschreven in assembler, en de software die ze gebruiker voor het herchecken van dir priemgetal is geschreven in C en daarnaas tis het ook op twee verschillende soorten platformen na gerekend.

Het getal is dus echt een Priem getal, en is tot op heden het 40ste Mersenne nummer. Echter dit is niet met 100% zekerheid aangezien er nog een aantal niet dubbel gecheckte openingen zijn in de range voor (2^20996011)-1 dan kan er pas met zekerheid verteld worden dat dit het 40ste Mersenne getal is.

Voor meer informatie kijk je maar op
www.mersenne.org
www.mersenneforum.org

[gnimmeL_kraD]

toch vraag ik me af waarom ze er zo lang over deden om er achter te komen dat het getal deelbaar was door 10... immers eindigen ALLE getallen die deelbaar zijn door 10 op een nul

[Anoniem: 38411]

hehe als je dat getal in kladblok zet, heb je een txt file van ongeveer 6 megabyte

[Anoniem: 89475]

Staat ook op de site.

Heeft iemand trouwens enig idee hoe dit getal offiecieel genoemd wordt????? Ik bedoel, 1904 heet negentienhondervier......

[Anoniem: 82810]

Naamgeving?

10^100 heet een Googol (goh, waar ken ik die naam van)
10^(10^100) heet een Googolplex. Dit is het grootste getal met naam (officieel). Zie http://www.fpx.de/fp/Fun/Googolplex/

Hiertussenin zitten niet echt meer namen, bij mijn weten. De naamgeving t/m 10^63 is niet zo moeilijk, gewoon de Romeinse getallen, met -joen en -jard per 3 nullen erachter (10^60 is dus deciljoen en 10^63 is deciljard).

Je kan trouwens ook priemgetallen downloaden van een link die op die site staat Voor als je wel breedband hebt, maar niet van films houd

[YopY]

2 tot de 20,996,011 -1ste macht. Ik kan het wel uitrekenen, maar ik heb geen rekenmachine die zo'n groot getal uit kan rekenen.

Edit: Laat maar, ik heb hem al gevonden op
http://mathworld.wolfram.com/news/2003-12-02/mersenne/mersenne40.txt
(klikken op eigen risico, 6 MB groot)

[Janoz]

Het is 2 tot de 20.996.011ste macht min 1. Van het getal dat jij noemt kan ik zo uit het blote hoofd al 20.996.009 factoren opschrijven

[Maxonic]

tip 1: gebruik dan geen kladblok

[Anoniem: 34844]

Dat gaan we vieren vanavond!

[Anoniem: 6104]

En hoe spreek je dat uit?? Dat lijkt me direct het langste woord ter wereld

[BaatZ]

we hebben maar Nederlandse woorden tot 10^15 (ziljoen, voor zover ik weet)
In de wetenschap gaan we nog iets verder tot 10^24 (peta, of was het exa?) maar daarna is er geen woord meer voor, tenzij je vermeningvuldigingen wil uitspreken

[Anoniem: 82384]

miljoen = miljoen ^ 1
miljard
biljoen = miljoen ^ 2
biljard
triljoen = miljoen ^ 3
triljard
quadriljoen = miljoen ^ 4
quadriljard
etc.

Je kunt dus behoorlijk makkelijk verder tellen.

centiljoen is zo bijvoorbeeld 1 miljoen ^ 100 ('cent' is immers 100)

En dan heb je nog getallen als googol en googolplex (waar ook de naam Google vandaan komt)

(Overigens staat bv. 'quadriljoen' ook gewoon in mijn Kramers NL woordenboek)

[Anoniem: 45450]

Na jouw post gelezen te hebben had ik even het briljante idee om scriptje te maken die googolplex berekent..

Het koste me een paar minuten om te bedenken dat ik eerst een nieuwe hardschijf nodig had van vele miljarden exabytes om alles op te slaan Daarnaast zou het me vele miljarden jaren kosten om de script uit te voeren

Er zijn in ons universum zelfs geen googolplex elektronen

edit: Mooi overizicht van alle grote priem getallen, inclusief mooie uitleg: http://www.utm.edu/research/primes/largest.html

[willemg21]

Sterker nog: er zijn niet eens googol electronen in het universum! Bij 10^86 (ongeveer; ik kan er een paar naast zitten ) houdt het allemaal wel op...

[Anoniem: 96271]

tweetotdemachtttwintigmiljoennegenhonderdzesennegentigduizendelfmineen

[Tupel]

Als je het uitspreekt en dat opschrijft wordt het toch een woord!! Eerst nadenken dan schrijven?

[Olaf van der Spek]

Nee, dan blijft het een getal.

[Anoniem: 9927]

Het woord auto is een woord ja, maar een auto blijft wel een auto...

Het woord 6.320.430 is ook geen getal, of ehhh..

[Deadsy]

oh jij bent zo iemand die alles viert?
doen wij ook. wij vieren elke bijzondere dag zoals Maandag enzo.

is dit echt een goede test om de cpu te stresen?
en die 100.000 is ook niet slecht.

[Anoniem: 92320]

$100.000,- is niet voor deze persoon !

Je krijgt dit bedrag als je het eerste priemgetal vind met meer dan 10 miljoen cijfers (lees: 10.000.000) deze jongen komt dus nog een nulletje te kort.
BUT..........."Don't give up the good work, son"

[Cergorach]

$100.000!?!?

*gaat het meteen installeren op alle pc op het bedrijfsnetwerk*

;-)

Just kidding!

[Anoniem: 94631]

Palm, ook bijzonder als er niets te vieren valt. Dat bier wordt zeker vooral verkocht aan mensen als jij

[Anoniem: 84327]

Wat als ik nu een miljard keer een één achter elkaar zit heb ik dan weer het grootste priemgetal ontdekt ?

[eggieman]

nee, sorry dat getal is deelbaar door 3
probeer het nog eens.

[Anoniem: 56618]

Niet door 3, wel door 11