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

Spanjaarden vinden nieuw patroon in priemgetallen

Twee Madrileense onderzoekers hebben een vooralsnog onopgemerkt patroon in de distributie van priemgetallen weten bloot te leggen. De ontdekking zou onder meer zijn weerslag op cryptografische beveiliging kunnen hebben.

De twee onderzoekers, Bartolo Luque en Lucas Lacasa van de Spaanse Universidad Politécnica de Madrid, ontdekten een tot dusverre onbekende wetmatigheid in de distributie van priemgetallen. Op het eerste gezicht lijken priemgetallen - getallen die alleen door zichzelf en door 1 deelbaar zijn, willen ze een geheel getal als quotiënt opleveren - willekeurig voor te komen. Mede hierdoor is het zoeken naar grote priemgetallen, die onder meer in de cryptografie gebruikt worden, een rekenintensief karwei: het is niet mogelijk om een computer aan de hand van een formule in een reeks getallen de priemgetallen aan te laten wijzen.

De twee Spaanse wiskundigen hebben ontdekt dat een verschijnsel dat als de Wet van Benford bekend staat, ook voor beperkte reeksen priemgetallen geldt. Deze wet stelt dat de verdeling van cijfers in willekeurige getalreeksen een logaritmische schaal volgt. Hoewel priemgetallen zich niet aan deze wet houden, lijken deelverzamelingen priemgetallen wel een generieke vorm van deze wet te volgen. Het duo ontdekte dat priemgetallen deze Generieke Wet van Benford volgen, waarbij het priemgetalstelling de verdeling van de eerste cijfers van de priemgetallen voorspelt. Bovendien hebben Luque en Lacasa vastgesteld dat de Riemann-hypothese, die voorspellingen over de verdeling van priemgetallen doet, zich eveneens aan de Generieke Wet van Benford houdt.

Het werk van de twee mathematici zou kunnen worden toegepast om verdelingen die niet aan de Wet van Benford voldoen met behulp van de Generieke Wet van Benford toch te structureren. Die generalisatie zou betekenen dat 'de' Wet van Benford slechts als een speciaal geval van de Generieke Wet van Benford gezien moet worden.

Het werk van de Spanjaarden zou de analyse van getalreeksen kunnen vereenvoudigen. Zo zouden bepaalde vormen van fraude, zoals het vervalsen van cijfers in een boekhouding, makkelijker bewezen kunnen worden: de 'natuurlijk ontstane' getalsverdeling in correcte boekhoudingen houdt zich normaliter aan de Wet van Benford, maar verdelingen van frauduleuze, dus verzonnen getallen niet.

Door Willem de Moor

Redacteur componenten

11-05-2009 • 19:18

135 Linkedin Google+

Submitter: bobwarley

Reacties (135)

Wijzig sortering
het is niet mogelijk om een computer aan de hand van een formule in een reeks getallen de priemgetallen aan te laten wijzen
Je kunt toch gewoon aangeven vanaf welk getal hij moet gaan rekenen? Of wordt dit niet bedoeld?
http://img11.imageshack.us/img11/395/priemgetallen.png
OK, nog een beetje verfijnd:
int MAX = Integer.MAX_VALUE; //Alle priems in int bereik
int SQRT_MAX = (int)Math.sqrt(MAX); //Genereer x-vouden tot de wortel
// init: stel alle oneven getallen zijn priem en 2 is ook priem
BitSet bs = new BitSet(MAX);
for (int i = 1; i< MAX; i+=2)
{
bs.set(i, true);
}
bs.set(2, true);

// loop over de zeef, 1,2 zijn priem. start met 3-vouden, 4-vouden
for (int xvoud = 3; xvoud <= SQRT_MAX; xvoud++)
{
// als priem, verwijder alle meervouden van priem
if (bs.get(xvoud))
{
for (int i = xvoud*xvoud; i <= MAX && i>0; i+=xvoud)
{
bs.set(i, false);
}
}
}
}

Beter ga ik hem niet krijgen denk ik :)
Ik begrijp de hele fascinatie voor priemgetallen eigenlijk niet. Is het dan zo bijzonder dat het alleen door zichzelf en door 1 is te delen (en als resultaat een geheel getal te krijgen) ? Misschien voor wat enigszins achterhaalde cryptografische methoden, maar voor de rest? Gehele getallen zijn gesimplificeerde eenheden bedacht door en voor mensen. Volgens mij doet de natuur niet zo moeilijk over gehele getallen. In dat opzicht is Phi (golden ratio) eigenlijk veel interessanter en belangrijker lijkt me en dit is geen geheel getal.

Nu zijn er dus een aantal spanjaarden bezig met het verzinnen van een wetmatigheid voor de distributie van door mensen verzonnen getallen die worden gebruikt in door mensen verzonnen wetmatigheden (divide by zero is niet mogelijk, is 1 wel een priemgetal of een eenheid, nul telt niet mee etc etc). Ze zijn m.a.w. eigenlijk wetmatigheden aan het zoeken in een door mensen uitgedacht model van de werkelijkheid. Veel succes zou ik zeggen..
Het is een voorbeeld waarvoor de Wet van Benford gebruikt zou kunnen worden.

Helaas is dit wel een bijzonder slecht voorbeeld doordat boekhouding voornamelijk door mensen wordt gedaan en mensen nu eenmaal fouten maken. Je kunt dus niet aantonen of er fraude in het spel is of simpelweg een fout.
Klopt in zekere zin. Sterker nog, je zou dezelfde theorie kunnen gebruiken om je in geval van opzet vrij te pleiten (dit soort 'beveiliging/bewijsvoering' moet je altijd 2 kanten op redeneren). Je moet dan wel goed in de materie zitten en eerst een analyse op de data loslaten waarmee je wilt frauderen en software vervolgens in de lijn van de Wet van Benford de bedragen laten generen.
De zwakheid in het boekhoud/ opsporingsvoorbeeld zit er in tegenstelling tot bijvoorbeeld DNA, dat je zelf een eenheid kan creëren of beïnvloeden. Volgens mij is het ook niet gezegd dat als je een boeking weglaat de verdeling niet meer klopt of aanmerkelijk minder waarschijnlijk wordt.
Maar je hebt wel meer kennis nodig om het in je voordeel te laten werken: je gaat van 'witte boorden'- naar 'witte jassen'-criminaliteit. En met hoe meer dingen een fraudeur rekening moet houden, hoe groter de kans dat hij ergens een fout maakt (ook een criminele nerd is feilbaar) - echter het omgekeerde geld dus ook. Hoe meer een accountant of zelfs rechter op zo'n tooltje vertrouwt, hoe groter de kans dat hij erdoor op het verkeerde been wordt gezet (teveel nadruk op elektronisch afluisteren heeft ook voor onnodige missers in inlichtingenwerk gezorgd).
Dit is iets wat de belastingdienst al jaren doet. Bij aangiftes kan worden bekeken hoe de getallen zijn opgebouwd, met name op welke cijfers ze eindigen. Mensen die fictieve getallen opgeven blijken neigingen te hebben ze te 'ontafronden' om een schijnnauwkeurigheid te presenteren en bij een opgeleverde cijferbrei zijn daar patronen in te ontdekken.

Als bewijs is het niet echt bruikbaar maar bij een bedrijfsadministratie kan indien er veel fouten zijn zo'n analyse worden gebruikt om een inschatting te maken of het gaat om onopzettelijke fouten of dat er opzet in het spel is.

Maar als meer dan ondersteunend moet je dit niet zien.
Ik snap er ook niet veel van. Cijfers die in het normale leven voorkomen zijn toch gewoon willekeurige getallen? Een getal in een boekhouding kan net zo goed 1000000 zijn als 1478231
Benford's law zegt dat er toch vaak een bepaald patroon in het eerste cijfer zit. Zo beginnen getallen veel vaker met een 1 dan met een 9. Men gaat er vanuit dat mensen (de 'fraudeurs') getallen ongeveer even vaak gebruiken. Dan voldoen ze niet meer aan de wet, waardoor je het kunt detecteren. Wel grappig dat de getallen die je noemt wel allebei met een 1 beginnen.

Zie bijvoorbeeld deze video voor een demonstratie en uitleg met real-world data :)

[Reactie gewijzigd door JanDM op 11 mei 2009 19:59]

Of copy-paste deze pagina in een bestand en gooi het volgende eroverheen:

grep -oE "[0123456789]+"|sort|cut -b 1|uniq -c


Zorg wel dat je een set hebt van 200+ getallen.

:)
voorlopig krijgen we dit:

96 0
348 1
350 2
109 3
60 4
64 5
22 6
34 7
19 8
14 9

Dus het klopt wel aardig :-)
Vele cryptografische beveiligingstechnieken (zoals RSA) steunen op het feit dat een processor/computer heel snel twee priemgetallen met elkaar kan vermenigvuldigen en er bewerkingen mee uitvoeren, maar niet opnieuw terug kan ontbinden in factoren, d.i. terug de originele priemgetallen te weten komen.

http://nl.wikipedia.org/wiki/RSA_(cryptografie)
Laten we RSA als voorbeeld nemen. Daarbij worden twee hele grote priemgetallen (die samen de basis zijn van de geheime sleutel) met elkaar vermenigvuldigd tot een getal n. Dat getal n is deel van de publieke sleutel. De veiligheid van RSA valt of staat met de rekenkracht die nodig is om uit n die twee geheime priemgetallen terug te vinden.

Als je daar in plaats van priemgetallen 'gewone' getallen zou gebruiken dan zou het terugvinden van die getallen vele malen eenvoudiger zijn. Die gewone getallen hebben namelijk een aantal delers (anders dan 1 en zichzelf) en het vinden van zo'n deler brengt je een hele grote stap dichter bij de oplossing. In het geval van priemgetallen zijn die delers er niet en moet je dus echt specifiek op zoek naar die twee geheime priemgetallen.

(Even afgezien van het feit dat er nog wel meer eigenschappen van priemgetallen benut worden in RSA.)

Kortom: door die 'ondeelbaarheid' hebben priemgetallen allerlei eigenschappen die bepaalde berekeningen (zoals het 'kraken' van een RSA sleutel) erg moeilijk maken en andere juist weer makkelijker. Het gaat een beetje te ver om dat hier tot in details uit te gaan leggen. Als je daar meer over wilt weten dan is er op internet vast een schat aan uitleg te vinden :)

[Reactie gewijzigd door Orion84 op 11 mei 2009 19:55]

Voor de mensend die graag een echt algoritme een keer willen bekijken:

Zie http://nl.wikipedia.org/wiki/RSA_(cryptografie) of http://nl.wikipedia.org/wiki/Rijndael_(cryptografie)

RSA = asymmetrisch
AES/Rijndael = symmetrisch

Dan heb je gelijk twee belangrijke varianten te pakken.
Jou bewijs klopt niet zoals AquillaP aangaf.
Het correcte bewijs :

Stel dat er een eindig aantal priemgetallen is, als je deze allemaal berekend en met elkaar vermenigvuldigt en dan 1 erbij optelt, dan heb je een nieuw priemgetal gevonden omdat dit nieuwe priemgetal niet door welk getal dan ook deelbaar zou zijn.
Het is inderdaad onzin dat het niet mogelijk is om uit een reeks getallen te bepalen welke daarvan priemgetallen zijn. En er zijn efficiëntere methoden om dat te doen dan jouw programmaatje...

Maar als de getallen heel erg groot zijn (bijvoorbeeld getallen van een paarhonderd cijfers), dan wordt het heel erg moeilijk om te bepalen of die getallen wel of niet priemgetallen zijn; d.w.z. het kost heel erg veel rekenwerk, zoveel dat het zelfs met de snelste supercomputers praktisch onmogelijk is.

Van die eigenschap van priemgetallen wordt gebruik gemaakt in cryptografie.

Als er, wat het punt is van het artikel, nieuwe patronen worden ontdekt in de priemgetallen, dan kan het wel eens zo zijn dat iemand een nieuw algoritme ontdekt om snel te testen of een willekeurig getal wel of niet een priemgetal is. En als dat kan, dan valt de huidige cryptografie in duigen - cryptografische sleutels kunnen dan makkelijk gekraakt worden.

Over je code: Dit is overbodig: if(huidiggetal % 1 == huidiggetal && huidiggetal % huidiggetal == 0) want dat is voor alle getallen true. Om het efficiënter te maken hoef je bijvoorbeeld alleen de oneven getallen tot de wortel van huidiggetal te testen (niet alle getallen van 2 t/m huidiggetal).

[Reactie gewijzigd door jj71 op 11 mei 2009 20:38]

Heel leuk, voor getallen die in een 32 of 64 bits integer passen. maar wat als het daar boven komt ?

overigens is:

if(huidiggetal % 1 == huidiggetal && huidiggetal % huidiggetal == 0)

niet de juiste oplossing is voor het probleem zoals jj71 al aangeeft.
Op MD5 zou ik tegenwoordig sowieso niet vertrouwen. http://mail.python.org/pi...004-September/281621.html
Het is in SSL prima mogelijk om voor andere crypto systemen dan RSA te kiezen voor de authenticatie en key exchange. Zie bijvoorbeeld:
http://en.wikipedia.org/w...ayer_Security#Description

Dat RSA op dit moment zo'n beetje de standaard is voor SSL certificaten is wel waar, maar het is niet zo dat er zonder RSA geen SSL mogelijk zou zijn :)
Vind ik nog al grof gesteld. Getallen (en priemgetallen) zijn in principe toch uit de wiskundige wetten voorkomende verschijnselen. Ik denk dat het vrij aannemelijk is dat wiskundige wetten net zo universeel zijn als natuurkundige wetten (of zelf nog meer, aangezien onze huidige natuurkundige wetten niet altijd blijken te blijven gelden: zie bijv. newton's wetten t.o.v. de rel. theorie)

Stel dat een ver buitenaardse beschaving ongeveer zo ontwikkeld zou zijn als wij. Waarschijnlijk zit hun samenleving, taal, gedrag etc. allemaal totaal verschillend in elkaar. Toch is 1+1 bij hen ook 2 (als zullen zij waarschijnlijk een ander getallensysteem kennen).
aanvulling: wij hebben decimale stelsel (10) omdat we 10 vingers hebben.. Verder gebruiken we 365 dagen omdat onze aarde er zo lang over doet. 12 maanden (vanwege de maan)
Een seconde is daarom afgeleid van onze baan om de zon. (al wordt het tegenwoordig vastgesteld in de trilling van een cesium atoom of zoiets)
Toen we electronica uitvonden, konden we maar 2 posities bedenken.. AAN en UIT (1 en 0).. dus binair.
Mocht een buitenaards ras 36 voelsprieten hebben, dan tellen ze waarschijnlijk met dat stelsel.
Mochten ze electronica of optonica hebben die in 3 posities kunnen staan, dan hebben ze een trinaire computer etc.
Welk stelsel je gebruikt, maakt niks uit voor de aantallen en heeft ook nauwelijks invloed op de wiskunde. Het is alleen een wijze van opschrijven van getallen.
Voorbeeld: zelfde sommetje in 3 getallenstelsel, komt toch allemaal zelfde antwoord uit hoor. en de + is eigenlijk ook niet verzonnen, maar is eerder afgeleid uit de natuur, voor die gevallen waarbij er meerdere dingen ineens bij elkaar komen....
Tuurlijk voor gemakzucht hebben we er een + van gemaakt en noemen we het optellen.

En we hebben het 10 stellig stelsel niet alleen vanwege onze 10 vingers, maar vooral omdat het stukken eenvoudiger te bedienen is dan de romeinse cijfers.


I+I= II
1+1=2
01+01=02

VI+V=XI
6+5=11
06+05=0B
Wacht even hoor. Het romeinse stelsel is van een hele andere categorie.

Decimaal, binary, hexadecimaal, maar ook base-3, base-5 etc, zijn allemaal mooie universele systemen met een vaste set tekens, en waarbij je de "volgende kolom" gaat gebruiken als de huidige kolom overloopt. Elke unit in een kolom heeft een universele waarde namelijk base^n waarbij n het kolom nr is (nr is base 0). Elke kolom verder naar links heeft dus op systematische wijze meer waarde dan de vorige.

In het romeinse systeem hebben kolommen geen waarde, je moet domweg dingen bij elkaar optellen. Operaties zijn veel moeilijker. Bijv. I + IIII = V (waarom V?) VI + IIII = X (waarom niet VV?) De regels zijn ingebakken en niet universeel.

Maar in decimaal: 1+9 = 10 Waarom? omdat er geen teken voor 10 is, en je dus 1 overdraagt naar de volgende kolom. Deze regel geldt altijd. Dus: 91 + 9 draagt 1 over naar de 2de kolom, en die 2de kolom daagt 1 over naar de derde, dus 100. :Y)
de maya's telden tot 20, de sommige natuur-culturen komen niet verder dan 3, daarachter gebruiken ze de term veel.

Het bijzondere is dat dit effect heeft op hun dagelijks leven: komen ze samen met 3 man, dan kunnen ze vertellen met hoeveel ze waren, waren ze met 4, dan waren ze met veel, abstract kunnen ze zeggen met hoeveel, en zullen ze niet het verschil zien tussen 4 of 5 of 6. Als ze op naam gaan bepalen natuurlijk wel.
Wij hebben dat ook vanaf een bepaalde grens, we waren met 10 of we waren met "veel". Waar ieder zijn grens ligt is relatief, en vooral eigen aan de omgeving waar je in leeft en gewent bent.

Heel oude culturen rekenden tot 60 daarom is onze tijd ook gebasserd op 60. 60 is niet zomaar een getal, het is toevallig een getal met vele delers, net als 24 en vele andere getallen, maar er zijn nog veel meer eigenschappen te vinden die het getal 60 bijzonder maken.
Ik heb daar eens een boek over gelezen, over hoe de mens heeft leren tellen, cijfers en getallen gebruiken en rangtelwoorden.

Het 60 tallig stelsel is afkomstig van de kootjes van de vingers:
er zijn 12 kootjes (op de 4 vingers, de duim wordt gebruikt om de kootjes aan te raken), en op het andere hand heeft men 5 vingers. Zo kan men dus tot 60 tellen met twee handen.

Verder is een priemgetal weinig "wiskundige wetten", voor zover bekend komen priemgetallen ook niet speciaal voor in de natuur. Op wikipedia staat er iets over één insect (terwijl er 10 miljard andere zijn).

Als ik morgen een "fastmangetal" uitroep dat alleen deelbaar is door 27 en zichzelf, hebben we dat ook en is het ook dat ook geen "wiskundige wet"
Toch is 1+1 bij hen ook 2
Daar zou ik niet zo zeker van zijn ;)
2 verbinden wij immers met een waarde, die gelijk staat aan het elementen die gepasseerd zijn om tot 2 te tellen. Het uitvinden van getallen en tellen is niet zo simpel als het lijkt, de mens heeft daar lang over gedaan en er zijn veel stappen geweest. 2 is een abstractie van 1, 2 (die staan dan al op een rangrij, dat is al een vooruitgang op: 1 en 1, niet plus!).

Verder mag je je niet blind staren op wat we zien :) Wij "denken" dat we de natuurwetten (die we zelf zo noemen) kunnen omschrijven in een theorie en die over hetzelfde is. Maar alles van deze theorieën is gebaseerd op wat we ervaren. En zoals een tekenfilm figuurtje niet door kan hebben dat er 3 dimensies zijn, zo zien wij misschien ook niet alles zoals het is; en zien we gewoon onze werkelijkheid.

[Reactie gewijzigd door ? ? op 12 mei 2009 09:12]

De manier hoe cijfers weergegeven worden is eigenlijk voor de meeste wiskundige dingen van bar weinig belang.

Voor veel dingen is het feit dat je kan optellen en vermenigvuldigen, en dat die twee bewerkingen aan een paar basisregels voldoen genoeg, zoals bijvoorbeeld:

(a + b) + c == a + (b + c)
(a * b) * c == a * (b * c)
a * (b + c) == a * b + a * c
a * 1 = a
a + 0 = a
a * (1/a) = 1
a + (-a) = 0

Het maakt dan niet uit of je gewend bent om met decimale getallen of met romeinse cijfers te rekenen Zolang die basis regels maar kloppen zal je hele bouwwerk daarbovenop ook blijven kloppen.

Dus of 1 + 1 bij hun ook 2 is is niet echt te zeggen, maar we zullen wel met aardige zekerheid kunnen zeggen dat het resultaat van "hun 1" + "hun 1" het zelfde zal zijn als het resultaat van "hun 4" / "hun 2"

[Reactie gewijzigd door LievenDenninger op 12 mei 2009 11:26]

Je bent al te ver. Jij hebt enerzijds al een abstractie van een voorwerp met een woord gemaakt. Daarna geef je een aantal weer met dat woord. Eerst moeten we leren tellen, door hebben dat 4 staat voor 1het eerste element, 2e, 3e, en dan het 4e .Wat is een aantal? Enz. Veel aannames.

Verder steunt de wiskunde die wij kennen op Axioma's. Dingen die als waar beschouwd worden zonder dat er bewijs voor hoef te zijn.

We spelen een spel met onze eigen opgestelde regels, zoals wij die denken te zien. Je moet vanuit psychologisch standpunt denken. Gewoon het kunnen optellen, rangorde toekennen en weten wat een plus is, heeft vele jaren geduurd. Ooit waren er mensen die dat niet konden. Of wel konden tellen, maar zo: 1, 2, 3, veel. En veel + veel = veel :-)
Dat is ook een systeem he.

En jij zegt dat je alles kan + - * / doen, dat zijn basisregels? Door ons uitgevonden, leunend op wat we zien en kunnen denken. Imaginaire getallen kende men vroeger ook niet en toch bestaan ze in onze wiskunde. Dus wat aliens doen met hun "rekenen" zou ik niet al te zeker over zijn.

[Reactie gewijzigd door ? ? op 12 mei 2009 13:00]

Ik ben het toch niet met je eens. Er zijn aannames in de wiskunde, maar veel zijn het er niet. Daarbij, als je ruimte wilt reizen zul je echt wel een geavanceerde wiskunde moeten hebben. Ik betwijfel of het mogelijk is zonder een systeem wat ruwweg op dat van ons lijkt. Met 1,2,3 en veel kom je niet ver... We zijn niet voor niets op het 10-tallig stelsel gesetteld. Niet dat het met romeinse of 12-tallige etc systemen allemaal niet kan, maar het is lastiger en inefficienter.
Mooi idee, dat "fastmangetal". Maar binnen het tientallig stelsel zal je het niet vinden, aangezien 27 deelbaar is door 3. Een getal wat deelbaar is door 27 is dus per definitie ook deelbaar door 3...
'Handig' is wat je gewend bent.
Als je van kinds af aan al gewend zou zijn aan een base-16 getallen reeks dan zou dat natuurlijk lijken.

Feit is dat getallenstelsels, om het even welke, ontzettend abstract zijn.

Base-10 lijkt voor ons ontzettend natuurlijk, maar dat is alleen omdat we er allemaal massief aan gewend zijn. Vanuit de natuur gezien zit er helemaal geen steek in een base-10 getallenstelsel.
Dat is nu net de reden van dit artikel.
Priemgetallen laten zich niet mooi van te voren uitrekenen.
Maar nu schijnt dat ietsjes gemakkelijker te gaan.
Maar ik vermoed maar een heel klein beetje gemakkelijker.
Denk eerder dat dit een storm in een glas water is.
En natuurlijk hebben ze een patroon.
Want het zijn steeds veelvouden van priemgetallen die geen priemgetal zijn.

[Reactie gewijzigd door MadButcher op 11 mei 2009 23:26]

Je beperkt inderdaad de keuze, maar daardoor wordt het niet makkelijker, maar moeilijker. Anders bestaat namelijk de kans dat je een getal als basis neemt, dat heel gemakkelijker te ontleden is. Je zou dan bijvoorbeeld ook toevallig 2^30 * 3^20 kunnen nemen, of iets vergelijkbaars, en dan heb je de delers zo gevonden. Het gaat er juist om dat je zeker wilt weten dat de delers van het getal erg groot zijn.

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 Elektrische 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