Priemgetallen misschien minder willekeurig dan gedacht

Nature weet ons te melden dat een groep natuurkundigen bij toeval heeft ontdekt dat priemgetallen waarschijnlijk veel minder willekeurig zijn dan voor alsnog werd aangenomen. Pradeep Kumar en een groep collega's ontdekten dit terwijl ze een programma voor het onderzoeken van hartritmes aan het testen waren. Hierbij viel hen iets op aan het verschil tussen opeenvolgende priemgetallen, namelijk dat de toename of afname van het verschil een vorm van eenheid bevat: bijna elk toename van het verschil tussen een priemgetal wordt gevolgd door eenzelfde afname. Een ander opvallend iets is dat de toename van het verschil een golflengte-beweging lijkt aan te nemen, met veelal een periode van drie. Dit was echter eerder ook al mensen opgevallen:

This finding is less surprising. Previous studies found period-6 oscillations in the histogram of distances between consecutive primes. Increments, remember, are differences between consecutive distances. The Boston team's findings are not supported by any kind of rigorous mathematical proof.

So sadly they can't shed any light on one of the biggest problems in maths: the Riemann hypothesis. This conjecture in number theory is intimately related to the distribution of primes. In 2001 the Clay Institute in the USA offered a prize of a million dollars for a proof of the Riemann hypothesis.

Reacties (69)

[T.T.]

Even de vragen te snel af zijn ;):
waarom is dit interessant?
Priemgetallen worden gebruikt in bijvoorbeeld cryptografie. Wanneer blijkt dat je priemgetallen ongeveer kunt voorspellen, hoef je veel minder priemgetallen te proberen en komt de cryptografische beveiliging in gevaar.

hoe werkt het precies?
Ze bestudeerden de eerste vijftig miljoen priemgetallen, de reeks die begint met 2, 3, 5, 7, 11, 13 en waarvan het grootst bekende meer dan vier miljoen cijfers telt. De volgorde van de intervallen (dus 1, 2, 2, 4 voor de eerste getallen)tussen die getallen bleek statistisch niet volkomen willekeurig.

[Emdicy]

Ik wil hier graag enige verbeteringen aanbrengen.

Waarom is dit interessant?
Dit is interessant omdat in veel modellen en simulaties gebruik wordt gemaakt van random nummers, waarvoor priem getallen worden gebruikt om ze te genereren. Dit kan dus betekenen dat simulaties waarvoor ervan uit wordt gegaan dat de gegeven input random is toch volgens een patroon worden uitgevoerd.

Voor cryptografie heeft dit weinig invloed. De priemgetallen die hiervoor gebruikt worden zijn allemaal al bekend. Het principe van cryptografie berust op het feit dat het ontbinden van een zeer groot getal in kleinere priemgetallen zeer moeilijk en tijdrovend is. Dat de priemgetallen, die dus al bekend zijn, een patroon volgen heeft hier geen invloed op.

Hoe werkt het precies?
Hier heb ik alleen toe te voegen dat het gaat om het verschil tussen de intervallen en niet om de intervallen zelf. Dus het gaat niet om 1,2,2,4, maar om de verschillen +1, 0, +2.

Reactie op puppetmaster:
Het tweede priemgetal, 2, heeft 1 cijfer. Het zesde priemgetal, 11, heeft 2 cijfers. Als je het zo bekijkt is het best mogelijk dat het vijftig miljoenste priemgetal vier miljoen cijfers heeft.

[Zarc.oh]

Volgens mij is 2 het eerste priemgetal, omdat een priemgetal per definitie door 2 getallen (1 EN zichzelf) deelbaar is, maar 1 is door 1 deelbaar en verder niet.

[Verwijderd]

Klopt wel, maar ik had begrepen dat 1 niet tot de priemgetallen wordt gerekend.
1 van de combinatoriek-theorieen is dat elk getal op de schrijven is als een uniek product van machten van priemgetallen (bijv: 84 = (2^2)*3*7 ).

Maar als 1 een priemgetal is, dan is 84 ook 1*(2^2)*3*7, of (1^2)*... en dus is er geen uniek product meer.

Maar misschien geldt de beperking, dat 1 geen priemgetal is, wel alleen in dit geval

[Verwijderd]

x=1
-----
x/1=1
x/x=1

[Reinier Jonker]

Twee getallen betekent niet twee verschillende getallen. Het gaat om specifiek 1 en het getal zelf, ongeacht de waarde van die getallen. 1 is deelbaar door 1 en door 1 (het getal zelf). Het is dus volgens de definitie een priemgetal

[Verwijderd]

Random nummers hebben niets met priem getallen te maken. Er zijn vele manieren om 'random' nummer te maken. En deze zullen nooit random zijn....Er is dus altijd een patroon in een random reeks getallen die gegenereerd is door een computer.

[Puppetmaster]

nu zit ik niet helemaal IN getallen enz.. maar hoe kunnen ze de eerste VIJFTIG MILJOEN priemgetallen bekijken en er dan achterkomen dat het grootste nu bekende een getal is met ca 4 miljoen cijfers?

er vanuit gaande dat priemgetallen hele getallen zijn natuurlijk he? (zijn ze toch ook?)

uitleg graag!

[zonoskar]

Die 50 mio is de som van het aantal priemgetallen. Waarvan het priemgetal met de grootste waarde 4mio cijfers heeft. Er zijn een hele hoop priemgetallen met 4 mio cijfers

[Puppetmaster]

yo bedankt! en Emdicy ook!
het kwartje is eindelijk gevallen...

[ACM]

1000 is een getal van 4 cijfers maar er kunnen maximaal 1000 priemgetallen inliggen (zijn er iets van honderd geloof ik)

Dus een getal van 4M cijfers kan prima het maximum zijn van de eerste 50M priemgetallen.

[Verwijderd]

Vergis ik me, of maakt dit sommige van de eerder onkraakbare beveiligingen wel kraakbaar?

[Verwijderd]

Ik denk het niet. Die onkraakbare versleutelde berichten zijn gebaseerd op RSA. De essentie van dat allegoritme is dat het product van twee grote priemgetallen zeer lastig is weer terug ontbinden in die twee factoren. Dat is dus hier niet aan de orde. Als hier verder aan wordt gewerkt kan wellicht worden mogelijk gemaakt om sneller priemgetallen te vinden, dan voorheen.
Echter het ontbinden van het product van twee priemgetallen in factoren blijft onverminderd lastig.

[Verwijderd]

Uhm is dit wel zo? Ik ben niet bekend met deze materie, maar het lijkt me dat als je relatief simpel een lijst met priemgetallen kunt aanleggen, dat je dan een dergelijke versleuteling wel heel erg makkelijk kunt breken. Je neemt gewoon het product, deelt dat door alle priemgetallen (kleiner dan de wortel van het product) en kijkt vervolgens of de uitkomst ook in de lijst met priemgetallen staat. Klinkt mij redelijk triviaal in de oren
Probleem kan natuurlijk zijn de gigantische hoeveelheid priemgetallen(in welke orde van grote liggen die producten?).
Of mis ik iets?

[zeroxcool]

Leuk leuk, hier hebben we ons profielwerkstuk over gedaan. Het is dus zo bij RSA dat je twee ontzettend grote priemgetallen neemt. Met grote bedoel ik priemgetallen rond de 2^64. Met deze twee priemgetallen maak je de private én de public key.

Er ligt dus zoals gezegd een verband tussen de public en de private key. Je zou dus aan de hand van de public key de private (secret) key uit kunnen rekenen, dit is een 'crack' methode die niet veel gebruikt wordt. Maar met dit mogelijk algoritme helpt het niet veel hoor. Misschien is er dan wel een regelmaat in de priemgetallen aanwezig, maar niet in de aangepaste keys. Daarom verwacht ik - en ja, ik ben geen wiskundige of natuurkundige - dat RSA of een ander encryptie algoritme dat met priemgetallen in gevaar komt.

De andere methode is voor elke secret key een waarde uitproberen, de 'brute-force' 'crack' methode. Dit doe je ook met je }:O'tje. Deze manier zal iets sneller gaan áls er een regelmaat in zou zitten. Je hebt immers sneller priemgetallen gevonden die je kan invullen in je 'brute-force' algoritme. Maar of dit echt in snelheid scheelt betwijfel ik, omdat er al ontzettend veel priemgetallen bekend zijn.

En al zou je er een regelmaat in vinden, dan blijf je gewoon grotere priemgetallen pakken. Priemgetallen met een grote van +/- 2^4096. Lang leve de wiskunde .

[Verwijderd]

Inderdaad, d'r zitten lichte patronen in de priemgetallen. Dus als je een paar priemgetallen hebt, dan kan je met wat grotere zekerheid gokken waar de volgende mischien zal zitten.

Maar RSA daarmee kraken is niet haalbaar. Je werkt dan met getallen van zo'n 300 (decimale) cijfers. Daar zijn er zo verrekte veel van. Rond de 10^300e zijn maar 1 op de miljoen cijfers een priemgetal. Dat zijn er dus "maar" 10^294! Dat zijn er verrekte veel.

De gepubliceerde vinding levert dus op dat als je er twee (of moeten het er drie zijn?) opeenvolgenden van de 10^294 hebt, dat je dan met beter dan 1 op miljoen kan voorspellen wat de volgende is. Dat helpt dus geen zier bij het ontbinden in factoren van een getal van 600 cijfers..... En dat laatste heb je nog steeds nodig om RSA te kraken.....

Rogier.

P.S. (hier dus [edit]) Dat "1 op miljoen" kunnen mensen die iets beter in de stof zitten tot op een paar decimalen uitrekenen. Ik weet het zelf niet precies. Het zal tussen 1 op honderd en 1 op miljoen zitten, maar verder "zit ik er niet ver naast". Het belangrijke is dat 2^294 of 2^298 nog steeds onhandelbaar grote getallen zijn.

[Verwijderd]

Je hebt immers sneller priemgetallen gevonden die je kan invullen in je 'brute-force' algoritme.

Klopt, maar aan de andere kant is het ook weer makkelijker om nog grotere priemgetallen te vinden die voor de versleuteling kan gebruiken. Dus de snelheidswints van het sneller vinden van priemgetallen ben je als kraker direct weer kwijt, omdat de versleutelaar ook sneller priemgetallen kan vinden.

[TD-er]

Die afschatting die je maakt (10³⁰⁰), dan heb je het over 1024 bits encryptie.
De keys die de eerste zoveel bits op 0 hebben staan (dus met een waarde << 2¹⁰²⁴) zullen niet zo vaak voorkomen, evenals keys die repeterend gedrag vertonen. (heb eens gehoord dat dat dan weer voor statistici interessant wordt) Op die manier vallen er al een heleboel keys af.

Verder wordt een dergelijke zware (1024 bits) encryptie (nog) niet zo vaak gebruikt. Voor de meeste interessante verbindingen, waarbij een snelle decryptie interessant is, (wireless lan bijvoorbeeld) wordt meestal maar effectief zo'n 96 bits gebruikt. (128 bits encryptie)
Dit laatste is natuurlijk een heel stuk sneller te kraken als er een patroon in de priemgetallen zit.

Een ander voordeel van een patroon in de priemgetallen is dat het ontbinden in factoren op een hele andere manier bepaald kan worden. Je zou dan namelijk makkelijker kunnen zeggen of 2 priemgetallen een beetje in de buurt komen van het ontvangen getal als je ze met elkaar vermenigvuldigd. Dat scheelt een hoop moeizaam verifiëren of de uitkomst van een deling ook werkelijk priem is.
Het aantal keys wat je op die manier per tijdseenheid kunt nagaan, is vele malen hoger dan wat nu het geval is.
Neemt niet weg dat zelfs 2¹⁰⁰ (willekeurig gekozen aantal) mogelijke keys doorzoeken nog een hoop tijd kost, zelfs al zou je er een 100 miljoen per seconde kunnen doen (= 10²⁵ seconde)

[PageFault]

RSA is al diverse malen gekraakt. In 1999 duurde het nog ruim een week om 256 bits sleutels te kraken. Ik weet niet in hoeverre de sleutellengte is toegenomen in verhouding tot de computerpower.

[Verwijderd]

het aantal priemgetallen is oneindig. Ze worden trouwens wel steeds 'zeldzamer'. Zo is bijvoorbeeld 25 procent van alle cijfers tussen 1 en 100 een priemgetal, maar als je kijkt naar de getallen 1 t/m 1 000 dan zakt dat percentage naar 17. En van de cijfers tussen 1 en 1.000.000 is nog slechts 7 procent deelbaar door één en zichzelf.
BRON: www.cijfers.net

owja... wie de priemgetallen wil zien, dit is een phpscriptje voor de priemgetallen tussen 0 en 10.000:

<?
$limit = 500;
$testen = 2;
while(true)
{
$testdiv = 2;
if ($testen > $limit)
break;
while (true)
{
if ($testdiv > sqrt($testen))
{
print "$testen ";
break;
}
if ($testen % $testdiv == 0)
break;
$testdiv = $testdiv + 1;
}
$testen = $testen + 1;
}
?>

[Verwijderd]

Bij dit linkje staan ze al alle 10k. DIt is ff gemakkelijker

[Nico de Vries]

Dat kan heel veel vlotter (alles < 10.000 in fractie van seconde):

$l = 10000;
for ($i=2; $i<=$l; $i++) {
if (!$m[$i]) {
echo "$i ";
for ($j=$i; $j<=$l; $j+=$i) $m[$j]=1;
}
}

[Verwijderd]

Lijkt erg op de Global-Scaling-Theory ( http://www.raum-energie-forschung.de/IREF-home-engl./Theor.htm ) van Dr. rer. nat. Hartmut Müller ( http://www.raum-energie-forschung.de/muell.htm )

Verdeling:
http://www.raum-energie-forschung.de/pcluster.gif
Software:
http://www.raum-energie-forschung.de/pcluster.sfx.exe

Ook zijn praktische toepassing G-com is veelbelovend een zender zonder draaggolf (zonder straling) ( http://www.raum-energie-forschung.de/IREF-home-engl./G_com1.htm )

[Barend]

Tot nu toe is elke vermeende regelmaat in priemgetallen bij nader inzien onjuist gebleken. Zal ditmaal ook wel weer zo zijn...

[Verwijderd]

Ik heb eens een artikel hierover in 'New scientist' of 'Scientific american' gelezen (weet niet zeker welke het nou was).

Wetenschappers hebben al wel enkele opzienbarende eigenschappen van priemgetallen vast weten te stellen, maar kunnen deze vooralsnog niet theoretisch onderbouwen, laat staan bewijzen.

Zo waren er in het artikel grafieken te zien, waarbij speciale priemgetallen (ja er zijn verschillende vormen) door een formule heen gingen en waarvan de uitkomst in een grafiek werden uitgetekend. Opvallend was dat in deze grafiek de uitkomst een kaarsrechte lijn volgde.

Er zit dus zeker structuur in deze cijferbrei en deze gebruiken voor doeleinden die random data nodig vereisen lijkt mij dus zeer onverstandig.

[Verwijderd]

Maar ondertussen zijn de meeste priemgetallen toch al uitgerekend. Deze hoef je toch niet meer uit te rekenen. Ze zijn reeds tot Mega-groot bekend. Is een regering od andere partij die over alle tot nu bekende priemgetallen beschikt niet in het voordeel ? Hoe lang doen zij erover om iets te ontcijferen in het geval dat zij de priemgetallen niet meer hoeven te "testen" maar gewoon kunnen aflopen ? Is hier iets over bekend ?

[Verwijderd]

om te kijken of een 65355 een priem getal is moet je (65355-1)/2 delingen doen, als er een ritme in zit hoe je alleen maar vooruit te rekenen van priem getal naar priem getal, en volgens mij zijn dat minder dan 32677 stappen.
Het zijn er ongeveer 6527.

[zeroxcool]

Wat jij probeert is te kijken of een priemgetal een Mersenne priemgetal is.
x = ({misschien Mpriemgetal} - 1) / 2
Als uit x ook een priemgetal komt, dan is het getal tussen de {} een Mersenne priemgetal.

De beste manier om te controleren of een priemgetal een priemgetal is kun je doen door middel van de manier die Euclides zo'n 2100 jaar geleden al bedacht heeft.

Stel je wilt weten of n een priemgetal is. Neem dan de wortel hieruit. Je pakt nu een lijst met bekende priemgetallen stel je neemt voor n 25. Je pakt de wortel uit 25, dat is natuurlijk 5. Je hoeft nu alleen maar 5 te delen door 5, 3 en 2. Komt hier een heel getal uit (zoals 5 / 5 = 1) dan weet je dat 25 geen priemgetal is.

We pakken nu voor n 199. We pakken de wortel hieruit, die is 14. We hoeven nu alleen maar te kijken of 11 te deelbaar is door 2, 3, 5, 7, 11 of 13. Bij alle delingen komt er geen heel getal uit, je weet dus zeker dat 199 wel een priemgetal is.

[Verwijderd]

ik vat je niet helemaal:

We pakken nu voor n 199. We pakken de wortel hieruit, die is 14.

De wortel van 199 is niet exact 14. 14x14=196.

We hoeven nu alleen maar te kijken of 11 te deelbaar is door 2, 3, 5, 7, 11 of 13.

De uitkomst van de wortel is 14. Waarom neem je dan het getal 11 om die te delen door andere priemgetallen?

Bij alle delingen komt er geen heel getal uit, je weet dus zeker dat 199 wel een priemgetal is.

11 gedeeld door 11 is geen geheel getal

Misschien kom ik een beetje zeikerig over, maar dat is niet me bedoeling. Ik weet zelf ook niet hoe het wel moet

[Verwijderd]

Das ook helemaal niet waar... om uit te rekenen of 65535 een priemgetal is moet je log2(65535) delingen doen... 256 dus... en niet 32767..

[Verwijderd]

Ik snap er echt geen reet van

[Verwijderd]

Nee hoor, je ziet zo ook al dat 65355 door 5 deelbaar is

[Verwijderd]

Hoe kun je "de meeste priemgetallen" uitrekenen als je oneindig door kan tellen ? Er komen natuurlijk steeds minder priemgetallen voor als je met grotere getallen werkt, maar het lijkt me stug dat je met zekerheid kan zeggen dat de meeste priemgetallen nu bekend zijn

[Verwijderd]

Het zijn er oneindig. Dat kan wiskundig bewezen worden. Het bewijs is zo simpel dat ik het even zal intikken:

STEL dat er een eindig aantal priemgetallen was. Dan konden we ze ALLEMAAL uitrekenen. Vermenigvuldig ze allemaal met mekaar, en tel er 1 bij op. Het resultaat is door GEEN ENKEL van de bekende priemgetallen deelbaar, en zou dus een priemgetal moeten zijn of anders door een nog onbekend priemgetal deelbaar moeten zijn. Er is dus altijd nog een groter priemgetal. Dus is het aantal priemgetallen oneindig.

ZIe mijn andere post om te begrijpen dat er VERREKTE veel priemgetallen zijn van 300 cijfers (die voor RSA gebruikt worden).

Rogier.

[Jefrey Lijffijt]

Dat klopt alleen als het daadwerkelijk zo is dat de vermenigvuldiging van priemgetallen met 1 erbij opgeteld ook een priemgetal is.
Misschien dat dat zo is, maar dat heb je nog niet bewezen.

[Munters]

Bij iedere delig houd je "rest 1" over.

[Verwijderd]

Ik hoop dat het volgende klopt:
-Dit zijn de eerste 20 priemgetallen: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71
-Het interval (verschil tussen 2 en 3, verschil tussen 3 en 5 etc) tussen deze getallen is: 1 2 2 4 2 4 2 4 6 2 6 4 2 4 6 6 2 6 6

Wat ik hiermee wil zeggen:
Ziet iemand nou een regelmaat tussen de laatste reeks getallen(de intervallen)? Als ik zo kijk dan klopt de theorie iig niet voor de 1e 20 getallen.

edit: ik snap wel dat 20 getallen niet genoeg zijn om een regelmaat vast te stellen. Waar ik dan ook meer op doel is dit:

Hierbij viel hen iets op aan het verschil tussen opeenvolgende priemgetallen, namelijk dat de toename of afname van het verschil een vorm van eenheid bevat: bijna elk toename van het verschil tussen een priemgetal wordt gevolgd door eenzelfde afname

<--dit zou volgens de eerste 20 getallen al helemaal niet kloppen (ook niet "bijna").

edit2 waarom is dit -1 gemod? misschien is het fout, maar het slaat wel ergens op. First post slaat helemaal nergens op

[nhimf]

Je vergeet een belangrijk priemgetal nl 1.
Veel mensen vergeten deze.

En als je de regelmaat wil onderzoeken, dan heb je echt wel meer dan 20 priem getallen nodig.

[windancer]

1 is per definitie geen priemgetal.

Dat dit zo is kun je ook afleiden uit het feit dat de bekende wiskundige uitspraak : elk geheel getal heeft een unieke priemontbinding.

Als 1 een priemgetal zou zijn zijn zowel 2*2*3 als 1*2*2*3 priemontbindingen van 12.

[Verwijderd]

Als je een priemgetal met een geheel getal vermenigvuldigt, is het resultaat nooit een priemgetal, dus 1 is geen priemgetal.

[Verwijderd]

Definitie priemgetal P:
not( E i : 1 < i < P : i | P ) ;
er is geen deler tussen 1 en P van getal P

dit moet je als echte tweaker wel kunnen dromen

[boesOne]

Het is ook een op statistiek gebaseerd vermoeden.. Dan praat je zowiezo in kansen en valt er van een schijnbaar willekeurige reeks toch best weer wat te zeggen...
Als je die verschillen in grafiekje zou weergeven en er zit in de puntenwolk een vaag golfvormigpatroon dan kan je toch wat beter zeggen waar ongeveer het volgende priemgetal zit.
Harde wiskundige functies moet je niet verwachten...

[Verwijderd]

Jij niet dan? Er zit toch duidelijk iets van een alternerende reeks in.

[witchdoc]

Niet 1 die jij kan zien in de hierboven gegeven opsomming!!

[Verwijderd]

kan jij dan die zessen verklaren, die imo op een willekeurige plaats staan

[CumpsD]

"met veelal een periode van drie"

"found period-6 oscillations"

was nu het verschil? 3 of 6, drukfout?

[ANdrode]

Osciliation = hele trilling.
Periode = tijd tussen 0 lijn passeren

1 Trilling heeft 2 keer een kruising met de 0 lijn ->
6 period oscillations, en elke 3 seconden een nieuwe periode

[aatos]

Volgens mij is een periode gewoon de hele trilling, en niet de tijd tussen het passeren van de nullijn.

Bovendien zou, als dat wel zo zou zijn, de 'periodes' 2 keer zo hoog zijn als de 'period oscillations'. In dit voorbeeld is de waarde juist de helft lager. Volgens jou definitie zouden 'period-6 oscillations' dus een periode van 12 hebben.

Ik denk toch eerder aan een tikfoutje.

[Verwijderd]

1 is wel degelijk een priemgetal, het is deelbaar door 1 en zichzelf (dat het toevallig ook 1 is, maakt niet uit)

En alle oneven getallen zijn priemgetallen ? Bij elke toename van 10, dus bv van 21 t/m 30, zijn er van de 5 oneven getallen 3 oneven getallen geen priemgetal. Vind ik niet echt een geval van alle oneven getallen zijn priemgetallen.

[zeroxcool]

En alle oneven getallen zijn priemgetallen?

Tuurlijk niet, maar dat had je al door. Wat wel waar is, is dat er maar één getal is dat even is én dat een priemgetal is. Dat is namelijk 2. 2 is dus het enigste even priemgetal.

[Proxy]

2 is deelbaar door 1, zichzelf en 2. Dat doet er volgens jou dus niet toe. Met andere woorden 4 is ook een priemgetal, want 4 is ook deelbaar door 1, zichzelf en 2.

[Verwijderd]

Nee, dat zegt hij niet, 2 is deelbaar door zichzelf. Dat dat 2 is maakt niets uit.

Dat jij dan over 4 begint slaat nergens op, want dan kunnen we alle 2^x ook priemgetallen noemen..

[JayVee]

Natuurkundigen hebben al eerder bewezen dat alle oneven getallen priemgetallen zijn:
1: klopt; 3: klopt; 5: klopt; 7: klopt; 9: meetfout; 11: klopt, 13: klopt; 15: meetfout; 17: klopt, 19:klopt ...

[Verwijderd]

Meten is weten