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

Patroon ontdekt in priemgetallen

Priemgetallen blijken minder willekeurig dan gedacht en laten zelfs een patroon zien. Dat ontdekten twee wiskundigen van Stanford University in de Verenigde Staten. Het blijkt zo te zijn dat priemgetallen die elkaar opvolgen, minder vaak hetzelfde nummer aan het eind hebben.

Dit laatste betekent dat een priemgetal dat op 1 eindigt minder vaak wordt gevolgd door een ander priemgetal eindigend op 1. Als priemgetallen willekeurig zouden zijn, zou dit niet het geval zijn. Nu zijn priemgetallen ook niet willekeurig, maar gedragen zich wel in veel opzichten zo. Wetenschappers beschouwen de opeenvolgende reeks priemgetallen als pseudowillekeurig omdat geen structuur aan te geven is waar in de reeks een priemgetal voorkomt. De onderzoekers Kannan Soundararajan en Robert Lemke Oliver ontdekten echter een afwijking in de willekeur, in eerste instantie bij het getal 1. Priemgetallen eindigen na 2 en 5 altijd op 1, 3, 7 of 9. Een priemgetal is een natuurlijk getal en alleen deelbaar door 1 en zichzelf.

De onderzoekers ontdekten dat in de eerste 100 miljoen priemgetallen een priemgetal eindigend op 1 in slechts 18,5 procent van de gevallen werd gevolgd door een ander priemgetal eindigend op 1. Als priemgetallen echt willekeurig zijn, zou het volgende getal in 25 procent van de gevallen op 1 moeten eindigen. Priemgetallen met een 9 op het eind volgden in 22 procent van de gevallen een priemgetal met een 1 op het eind op. Priemgetallen die eindigen met een 7 of 3 komen ieder 30 procent voor.

Eenzelfde patroon bleek voor priemgetallen eindigend op 3, 7 en 9 te gelden: die werden eveneens het minst vaak opgevolgd door een priemgetal eindigend op hetzelfde cijfer. Ondanks dat het patroon minder sterk wordt bij hogere priemgetallen - de onderzoekers checkten getallen tot een paar biljoen - bleef de afwijking zichtbaar.

Soundararajan kreeg het idee dit te onderzoeken na een lezing over tossen. In de lezing werd gesteld dat als Alice een munt tost totdat ze een kop door een munt gevolgd ziet, en Bob een munt tost totdat hij twee koppen achter elkaar ziet, Alice dan gemiddeld vier keer zal moeten tossen, tegen zes keer tossen voor Bob.

Soundararajan vroeg zich af of dit vreemde fenomeen zich ook op andere terreinen voordoet. Omdat hij al jaren met priemgetallen bezig is, besloot hij te kijken of hier hetzelfde aan de hand is. Dat bleek inderdaad het geval. Hij keek naar priemgetallen met grondtal 3, waarbij grofweg de helft van de priemgetallen op 1 en de helft op 2 eindigt. Priemgetallen onder 1000 in base 3 die eindigden op 1 werden meer dan twee keer zo veel gevolgd door een priemgetal eindigend op 2, en vice versa.

Nadat Soundararajan zijn bevindingen liet zien aan Oliver, schreef die een programma om veel verder langs de lijn van priemgetallen te kunnen zoeken; namelijk door de eerste 400 miljard priemgetallen. Dat toonde hetzelfde aan. Ook bleek dit niet alleen het geval te zijn voor grondtal 3 en 10, maar ook voor andere grondtallen.

Waarom het laatste cijfer van een priemgetal niet willekeurig verdeeld lijkt te zijn, is niet helemaal duidelijk. De onderzoekers vermoeden dat het te doen heeft met hoe vaak paren, groepen van drie en grotere groepen van priemgetallen voorkomen, zoals voorspeld door het k-tuple-vermoeden.

Volgens de onderzoekers lijkt hun vinding geen invloed te hebben op praktisch gebruik van priemgetallen, zoals voor cryptografie.

De paper is te vinden op de arXiv-server.

Door Krijn Soeteman

Freelanceredacteur

15-03-2016 • 18:15

134 Linkedin Google+

Reacties (134)

Wijzig sortering
Grootste priemgetal tot nu toe gevonden, 2 tot de macht 74.207.281 − 1. 8)7

Dat meldt de Great Internet Mersenne Prime Search (GIMPS), een project waarbij talloze particulieren en onderzoekers over de hele wereld hun computers beschikbaar stellen om naar nieuwe priemgetallen te zoeken.

http://www.mersenne.org/primes/?press=M74207281
Volgens de onderzoekers lijkt hun vinding geen invloed te hebben op praktisch gebruik van priemgetallen, zoals voor cryptografie.
Helemaal niets, maar alles voor de wetenschap!
Nu nog niet, maar als er daadwerkelijk een patroon te vinden is en ze vinden dat patroon ook, dan zal dat zeker wel flinke impact hebben voor cryptografie volgens mij (correct me if I'm wrong).

Als je via dat patroon snel een lijst van priemgetallen kunt maken, kun je volgens mij de private key vinden door deze priemgetallen te gebruiken. Het blijft een brute force, maar zal zoveel sneller zijn dan wat we nu hebben, dat het zeker wel haalbaar is.
Ik hoop dat we nu niet onze encryptiestandaarden hoeven weg te gooien...
Ik hoop dat we nu niet onze encryptiestandaarden hoeven weg te gooien...
Nee, want
Volgens de onderzoekers lijkt hun vinding geen invloed te hebben op praktisch gebruik van priemgetallen, zoals voor cryptografie.
en RSA is sowieso al een beetje achterhaald. Niet als in gekraakt of te zwak (nog niet althans) maar inefficiënt. Moderne c.q. betere encryptie werkt niet meer op basis van priemgetallen maar elliptische krommen.
een priemgetal is toch oneindig?
Nee, er zijn oneindig veel priemgetallen. Oneindig is geen priemgetal, en een enkel priemgetal is niet oneindig.
"oneindig" is alleen deelbaar door 1 of zichzelf inderdaad :Y)
Mis ik hier iets?
Soundararajan vroeg zich af of dit vreemde fenomeen zich ook op andere terreinen voordoet. Omdat hij al jaren met priemgetallen bezig is, besloot hij te kijken of hier hetzelfde aan de hand is. Dat bleek inderdaad het geval. Hij keek naar priemgetallen met grondtal 3, waarbij grofweg de helft van de priemgetallen op 1 en de helft op 2 eindigt. Priemgetallen onder 1000 in base 3 die eindigden op 1 werden meer dan twee keer zo veel gevolgd door een priemgetal eindigend op 2, en vice versa.
Hoe kan een priemgetal nu op 2 eindigen?
dat klopt inderdaad niet. alleen de single digit " 2" Is een priemgetal.

in delijst van priemgetallen eindigd geen enkel getal op 2.
Het gaat hier om base 3 of trinair stelsel, dus ieder cijfer is 0, 1 of 2.
ah, ok.
dat miste ik dus.
Thanx
Het gaat hier om priemgetallen uitgedrukt in het drietallig stelsel, in plaats van het gebruikelijke tientallige stelsel. In het drietallig stelsel tel je als volgt:
1 (een), 2 (twee), 10 (drie), 11(vier), 12 (vijf), 20 (zes), 21(zeven), 22 (acht), 100 (negen), ...
In het drietallig stelsel wordt het priemgetal vijf dus geschreven met een 2 op het eind.
Ook in andere oneventallige stelsels kan een priemgetal groter dan twee op een 2 eindigen.
Ik moet aan de film http://m.imdb.com/title/tt0138704/ pi denken waarin een wiskundige het geheim van het universum ontdekt.
Zo nou nog even een statistiekje op het een-na-laatste cijfer van een berg priemgetallen en we staan weer in de krant.
Er zijn wel langer patronen bekend in het voorkomen van priemgetallen, dat gaat dan wel niet over de daadwerkelijke getallen zelf, maar vond dat zelf ook interessant.
Zie https://nl.wikipedia.org/wiki/Spiraal_van_Ulam
Als het patroon lijkt af te nemen bij grotere getallen, wil dat dan niet zeggen dat als je maar lang genoeg doortrekt, het patroon zou verdwijnen? Ik vind het artikel wel erg summier.
Het zal nooit volledig verwijnen denk ik.

Ik denk dat je het kunt zien als iets door de helft doen:
1
0,5
0,25
0,125
...

Het zal nooit volledig verwijden.
Als je n naar oneindig gaat, gaat je uitkomt naar 0. Verdwijnt dus juist. Het gemiddelde van je reeks is dus 0. Precies wat ik bedoel te zeggen.
De uitkomst zal 0 benaderen maar het nooit worden.
Ze hebben het over priemgetallen die eindigen op 2, of lees ik het verkeerd.

Volgens mij is er (3x nageteld) 1 priemgetal eindigend op 2.
Bij base 3 niet. Dat is dus tellen tot 3 en dan komt 10. 1 2 10 11 12 20 21 22 30. Zou er lekker overheen lezen. Is niet zo boeiend verder :p

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 Huawei

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