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

Door , , 135 reacties
Submitter: bobwarley

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.

Benford-verdeling
Moderatie-faq Wijzig weergave

Reacties (135)

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..
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.
Ben ik de enige die niet snapt wat dit hiermee te maken heeft?
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).
Men kijkt dan ook hoe groot de afwijking van die wet is. Helemaal geen afwijking zou juist een indicatie kunnen zijn dat er iemand sjoemelt die die wet wel kent maar niet snapt dat het niet te perfect mag kloppen.

En het is natuurlijk maar een indicatie dat er fraude gepleegd is, geen bewijs. Maar zo weet je waar je met een grotere kans op succes kunt gaan zoeken.
Ik bedenk me nu dat het boekhoudvoorbeeld waarschijnlijk totaal onzinnig is. In tegenstelling tot bijvoorbeeld encryptie (het domein van hash-functies, priemgetallen, random numbers) zijn getallen in een boekhouding sowieso door mensen bepaald (niemand bepaalt een prijs/salaris/afschrijving aan de hand van een random number-generator). Of een fraudeur of iemend die een offerte maakt/afschrijving bedenkt/salaris bepaalt een bedrag bedenkt is in dit geval niet onderscheidend.
Helaas, anders was het bijvoorbeeld leuk geweest voor de Nma in geval van ingenieuze schaduwboekhoudingen .. (gemaakt voordat dit soort inzichten bekend werden).
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
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 :-)
Nee, de natuur lijkt random, maar bijvoorbeeld de fibonacci reeks komt op meerdere plekken in de natuur voor.

http://en.wikipedia.org/w...bonacci_numbers_in_nature
Als mensen getallen gaan verzinnen zijn ze namelijk ineens niet meer zo random. Zo fantasierijk zijn fraudeurs meestal niet. En dat soort partronen zijn herkenbaar.
Een kloppende boekhouding staat anders ook vol met door mensen verzonnen getallen: prijzen van de producten die je verkoopt, prijzen van de producten die je koopt, salarissen, enz.
In de serie Numb3rs ( fictie ) is daar eens een keer stuk over geweest.

http://nuweb2.neu.edu/mat...year=2006&date=2006-02-04
http://nuweb2.neu.edu/mat...year=2006&date=2006-02-05

Ondanks dat de serie fictie is, gooien ze daar wel met echt wiskundige en natuurkundige wetten. En leggen ze het uit zoals je het een kleuter zou uitleggen, met ook dezelfde diepgang :P
De film Pi (ja alsin de griekse letter, 3.14...) is denk ik een grote inspiratiebron voor numb3rs, daar ook word dus pi en dergelijken vergeleken met patronen in de natuur (de beurs in dit geval). Hele wazige maar wel vette film, kijken waard

http://en.wikipedia.org/wiki/Pi_(film)
het gaat om de verhouding van de eerste getallen in cijfers. het geldt alleen voor natuurlijke getallen, bijvoorbeeld (ik noem maar wat) de kilometerstanden van een x aantal willekeurige auto's van allerlei verschillende jaren.

je zult zien dat in de kilometerstand de 1 zes keer vaker voorkomt dan de 9 als eerste getal.
Volgens wikipedia: Een priemgetal is een natuurlijk getal groter dan 1 dat slechts deelbaar is door 1 en door zichzelf.

Op zich begrijpbaar maar wat is daar nu het nut van? :S Wat zijn de voordelen ervan, waarom is een priemgetal zo belangrijk onderwerp in de wiskunde?
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]

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.
Het probleem bij "gewone" getallen is eveneens dat meerdere 'basigetallen' tot hezelfde getal leiden bij vermenigvuldiging. Neem nou bijvoorbeeld het getal 36, dat kan je vormen uit 36 en 1, 2 en 18, 3 en 12, 4 en 9 etc etc...
Cryptografie is een belangrijke toepassing. Ik weet het fijne er niet van, maar ik kan me wel voorstellen dat je gegevens het beste kunt "scramblen" door ze met een getal te vermenigvuldigen dat niet zomaar deelbaar is. De gecodeerde data word zo nog "chaotischer" en het is veel moeilijker om patronen te ontdekken.
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.
@et36s:

Een ander nuttig gebruik voor een priemgetal is bijvoorbeeld het doorlopen van een verzameling natuurlijke getallen in een niet oplopende volgorde zonder een herhaling te hebben.

Het punt wat je wel goed overbrengt is dat priemgetallen itt veel van de uitvindingen van de mens niet zijn uitgevonden met een praktisch doel in het oog. Het was gewoon een opmerkelijke eigenschap van getallen die opgemerkt werd.

Overigens is het wel bewezen dat er oneindig veel priemgetallen zijn, een priem + de volgende priem + 1 geeft namelijk ook weer een priemgetal.
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.
priem+volgende priem + 1 = priem?

2+3+1= 6
3+5+1= 9....
In eerste instantie omdat het voor de leek nog redelijk te begrijpen is... daarnaast omdat het intrigerend is dat er geen patroon in zit, dus dat we (nog steeds) niet de priemgetallen kunnen "uitrekenen", ze volgen alleen uit "proberen".
e is ook een heel belangrijk wiskundig getal, maar dat begrijpt de leek al minder, of pi, iets bekender, enz...
"het is niet mogelijk om een computer aan de hand van een formule in een reeks getallen de priemgetallen aan te laten wijzen."

Dit is toch niet zo heel moeilijk :|
Even uit mijn hoofd: (zonder te compilen)

List lijstgetallen = new List<Integer>();
List priemgetallen = new List<Integer();
int teller =0;

for(int i=0;i<lijstgetallen.length;i++)
{
int huidiggetal = lijstgetallen.get(i);
if(huidiggetal % 1 == huidiggetal && huidiggetal % huidiggetal == 0)
{
for(int j=2;j<huidiggetal;j++)
{
if(huidiggetal % j =0)
{
teller++;
}
}
if(teller == 0)
{
priemgetallen.add(huidiggetal);
}
}
}

Zal mss een schoonheidsfoutj inzitten, maar zo is het toch ongeveer :)
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.
Dat is geen formule. In een formule kun je een invoerwaarde stoppen die de volgende uitvoerwaarde tot gevolg heeft.
Ook dat lijkt me geen goede definitie. Functionele programmeertalen voldoen bijvoorbeeld wel aan het criterium gegeven invoer, geef uitvoer. (Zonder zelf een toestand te definieren en te veranderen), en zijn wel degelijk wel Turing compleet. Daarom zouden ze alles kunnen wat TIZon met zijn C skillz ook kan.
Dat is gewoon brute-forcen en werkt leuk tot getallen van 4 of 5 cijfers of als je een beetje geduld hebt voor getallen van 10 tot 15 cijfers, maar daarboven wordt het toch echt innefficient.
Dat is geen formule, dat is alle getallen 'bruteforcen' om te kijken of het een priem is, wanneer je getallen hebt met 10, 20, 30 cijfers. Dan gaat jou programma wel erg langzaam nieuwe priemgetallen vinden ;)
Dat werkt wel, maar je vergeet dat een nuttig priemgetal (als in, voor encryptie) honderden cijfers heeft.
Voordat jouw algoritme daar in de buurt komt is het 10 miljoen jaar later :P
Het is niet moeilijk nee, maar voor hele grote priemgetallen is het heel veel werk, onpraktisch veel werk. Tenzij men een snellere methode weet te vinden.
En als je voor dit een probleem een oplossing zou vinden, en de veiligsheidsdiensten krijgen hier lucht van, dan heb je denk ik geen leven meer.
Dit zou de ultieme hack zijn!
Een algoritme is geen algebraÔsche formule
Zou dit betekenen dat we na MD5 en SHA-1 hashing helemaal niet meer kunnen vertrouwen?
Op MD5 zou ik tegenwoordig sowieso niet vertrouwen. http://mail.python.org/pi...004-September/281621.html
Het is een kleine voorspelling, waarbij het 1e deel getallen de ordering van die getallen bepaald. Dus niet veel met het hele getal.
Bovendien is SHA-1 allang niet meer te vertrouwen. En MD5 is snel te kraken met een bruteforce met uitgebreid woordenboek.
MD5 moet je dan ook niet gebruiken zonder een salt.
Waarom zou sha1 niet meer te vertrouwen zijn?
Een recente doorbraak laat het toe om collisions te berekenen met 2^53 berekeningen. Dat is te doen - single DES is niet gekraakt, maar puur vanwege de korte keylengte van 2^56 wist de FSF jaren geleden al een DES cracker te bouwen die het binnen enkele uren kan brute-forcen. De NSA kan het dan dus zeker, die hebben "iets" meer budget dan de FSF.
De EFF, niet de FSF. http://en.wikipedia.org/wiki/EFF_DES_cracker Ik geloof niet dat die chips open source, pardon vrije software draaiden ;)
Zelfs als de software niet open source is kan het niet meer zo heel moeilijk zijn om een brute force cracker te maken die dat wel is. Het is bewezen dat het kan de berekening die er voor nodig is is nu ook weer niet echt geheim te noemen en dus is het enige dat je nog hoeft te doen een zo optimaal mogenlijke code schrijven. Als de EFF matematici kan vinden die het algoritme kunnen bedenken dan zijn er zeker weten ook andere mensen die dat kunnen.

De reden dat niemand dat doet is omdat het gewoon niet langer echt interesant is, het is al gedaan en dus is het tijd voor een volgende beveiliging, dat is veel leuker om te doen dan iemand anders werk na apen.
En MD5 is snel te kraken met een bruteforce met uitgebreid woordenboek.
nou nou, dat valt ook allemaal wel mee. Het is van veel meer afhankelijk dan van puur een lang woordenboek. Lengte van de data die versleuteld is en salts bijvoorbeeld. Het is echt niet zo dat het per definitie erg makkelijk te kraken is.
MD5 is in 1 project met bruteforce in een maandje gekraakt een paar jaar geleden.
Nu zal dat dus binnen een week met gemak kunnen.

Er was zelfs een project waarmee men via een webpagina kon meerekenen

[Reactie gewijzigd door gp500 op 11 mei 2009 20:56]

Door dat de PC als maar sneller worden, is de tijd die nodig is om bruteforces nodig heeft klein en kleiner.

MD5 is dag van vandaag zelfs mogelijk via VGA's (die cuda ondersteunen). Die zijn nog pakken sneller dan via CPU

Hier is oud voorbeeld, weetende da GTX295 stukken sneller is dan 1 8800GTXje
http://www.dvhardware.net/news/elcomsoft_cuda_recovery.jpg
Inderdaad, als je woordenboek maar groot genoeg is voor 'hashmethode x' kan je stellen dat dus elke hasmethode makkelijke te kraken is?

Nee, makkelijke wachtwoorden zijn makkelijk te bruteforcen. Dat heeft niets met het feit te maken of hij dan al wel niet of wel gehashed wordt.
Het is een kleine voorspelling, waarbij het 1e deel getallen de ordering van die getallen bepaald. Dus niet veel met het hele getal.
Bovendien is SHA-1 allang niet meer te vertrouwen. En MD5 is snel te kraken met een bruteforce met uitgebreid woordenboek.
maar md5 is dan ook geen encryptie volgens mij.
MD5 is een hashing algorythm, geen encryptie inderdaad. Het verschil is dat encrypted data ge-decrypted kan worden, en hashed data niet. Twee verschillende methodes dus, met twee verschillende doelen.
Hashing heeft niks met priemgetallen te maken. Het gaat voornamelijk om public key crypto zoals RSA, El Gamal, etc. (Toepassingen zijn bijvoorbeeld ssl)

[Reactie gewijzigd door Data-base op 11 mei 2009 19:28]

El Gamal encryptie is gebaseerd op het Discrete Logarithm principe en heeft zodoende niet bijster veel met priemgetallen te maken.

SSL maakt ook maar in beperkte mate gebruik van RSA, enkel voor de ondertekening van Certificaten en voor het vercijferen van een zeer beperkt aantal berichten tijdens het opzetten van de SSL verbinding (key exchange). Daarna wordt over het algemeen overgeschakeld op AES.
SSL is effectief volledig afhankelijk van RSA. Geen RSA = geen key exchange = geen SSL.
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 :)
Er zijn wel connecties: als het discrete logarithme probleem, waar de sterkte van ElGamal vanaf hangt, zwak blijkt te zijn, kun je ook snel (beter dan brute force) factoriseren. Omgekeerd is dat niet zo, sneller factoriseren is, voor zover nu bekend, geen indicatie dat het discrete log probleem ook sneller door te rekenen zou zijn.
Benford's law vind ik nog steeds maar iets " geks" in de natuur. Is het bekend waarom benfords law opgaat? Of is het gewoon een feit, punt! ?
Wat ik raar vind, is dat we zelf wiskunde uitgevonden hebben (de nummertjes) en zelf priemgetallen uitvinden (lijkt me niet een natuurkundige term) en dan al 2000 jaar sukkelen om er wat te vinden. :+
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.
Denk niet dat je het zo eenvoudig kunt stellen.
De SumeriŽrs en later de Byzantijnen hadden een 60 tallig stelsel. Weinig mensen hebben 60 vingers...
Las net ook op http://en.wikipedia.org/wiki/Hour dat je eenvoudig op iedere hand tot 12 kunt tellen door met je duim de vingerkootjes af te tellen. Geinig!
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.
Waarom is decimaal dan precies efficiŽnt? Als we binair klakkeloos konden lezen en praten, dan zou de communicatie met machines een stuk gemakkelijker zijn (geen moeilijke programmeertalen en compilers nodig). Naar werken we met een inefficiŽnt stelsel, maar moeten we wel, omdat we nog te beperkt zijn door onze eigen geest.
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.
Ben ik het dus niet mee eens. Ik denk dat de kans erg groot is als die aliens ook een heel systeem van logica gemaakt hebben, dat in principe helemaal consistent is, dat de kans dan erg groot is dat er ergens de ons bekende bewerkingen optellen en aftrekken te vinden moeten zijn (misschien niet als axioma, maar afgeleid van hun eigen, andere axioma's), en het maakt dan niet uit maakt wat je er in stopt, de voor ons bekende gelijkheden zullen daar ook in te herkennen moeten zijn. Tellen zelf is daarvoor niet eens een vereiste (hoewel het in ons geval natuurlijk wel het gene is waar de wiskunde uit geevolueert is)
Verder steunt de wiskunde die wij kennen op Axioma's. Dingen die als waar beschouwd worden zonder dat er bewijs voor hoef te zijn.
Klopt, maar die axiomas zijn vaak toch wel zo basaal dat ze intuitief als waar aangenomen kunnen worden (en als ze dat uiteindelijk toch niet zouden zijn, dan zouden we snel genoeg tegen een contradictie aangelopen 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.
In princiepe klopt het natuurlijk dat wij optellen en vermenigvuldigen min of meer bedacht hebben, maar het feit dat het de basis vormt voor zo'n groot logisch systeem, dat helemaal consistent is geeft toch wel aan dat er wel iets van een absolute waarheid in moet zitten. En zelfs als we met hele andere axioma's begonnen zouden zijn (die geen tegenstrijdigheden zouden veroorzaken), denk ik dat het erg waarschijnlijk is dat we, waarschijnlijk via een hele andere benadering, op een systeem zouden uitkomen dat heel veel overeenkomsten zou hebben met het huidige.

Leuk voorbeeld is bijvoorbeeld de geometrische algebra, waar een "geometrisch product" gedefineerd wordt op min of meer de volgende manier:

als e1 en e2 twee vectoren zijn die loodrecht op elkaar staan, en een lengte van 1 hebben, dan:

e2 * e1 = -e1 * e2
e1 * e1 = 1
e2 * e2 = 1

Elke vector kan ook nog met een scalar vermenigvuldigt worden, wat, in tegenstelling tot het vermenigvuldigen van twee vectoren, ook nog commutatief is (ie a * b == b * a).

Verder gelden alle regeltjes uit mijn bovenstaande post hier ook.

En wat blijkt, een systeem dat volledig gelijk is aan de complexe getallen ontstaat logischerwijs als een onderdeel van dit systeem (net als dat van de quaternions overigens).
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.
Dat is natuurlijk ook een leuk systeem, maar ik daag je uit om ook maar iets van bruikbare axiomas op dat systeem te defineren, die niet heel snel contradicties veroorzaken.

[Reactie gewijzigd door LievenDenninger op 12 mei 2009 18:15]

a * (1/a) = 1
Voor a =/= 0 ;-)
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...
Echte tweakers tellen met hun vingers tot 1023 ;) Alleen jammer dat 4 er zo vervelend uit ziet...
En als je met de vingerkootjes binair zou tellen kan je gaan tot 16 777 215. Wie durft dan nog te zeggen dat op je vingers tellen niet ver gaat? :)

[Reactie gewijzigd door MGiles op 12 mei 2009 10:00]

Heb je daar een bron voor of zeg je gewoon maar wat? Volgens mij is het ook 'gewoon handig'. Het is deels gewenning misschien, maar het lijkt me sterk dat even makkelijk in hexadecimaal zouden kunnen rekenen als in decimaal.
Nu hebben we 102 = 100, in hexadecimaal zouden we hebben 102 = 100 (hex) = 256 (dec). Lijkt me niet geweldig praktisch rekenen.

Andere dingen (behalve de seconde) klinken wat aannemelijker.
'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.
Volgens mij is vanuit de wiskunde gezien het tientallig stelsel wel het eenvoudigste hoor...
Wat is er dan bijvoorbeeld zo veel eenvoudiger aan?
0x102 = 0x100. Ik denk dat in hexadecimalen 102 exact even moeilijk uit te rekenen is als in decimalen. Binair: 10 x 10 = 100 (2x2=4).

Mooi staaltje menselijkheid: wat anders lijkt, is moeilijk.
Elk getallenstelsel is in z'n eigen notatie een 10-stelsel.
2 in het binaire stelsel is 10.
16 in het hexadecimale stelsel is 10.
Mersenne heeft toch ooit volgende stelling geponeerd:

als n een priemgetal is, dan is 2^n - 1 ook een priemgetal

Deze stelling levert weliswaar niet alle priemgetallen, maar wel een oneindoge reeks.
wat een bullshit...

2^11 - 1 = 2047, deelbaar door 1, 23 en 89 (en 2047).

[Reactie gewijzigd door justinkb op 11 mei 2009 22:54]

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]

2^8 = 256
256-1 = 255
255/5 = 51

deze stelling levert geen priemgetallen.

2^0 = 1 [0]
2^1 = 2 [1]
2^2 = 4 [3]
2^3 = 8 [7]
2^4 = 16 [15] 3x5
2^5 = 32 [31]
2^6 = 64 [63] 3x21
2^7 = 128 [127]
2^8 = 256 [255] 3x 85
2^9 = 512 [511]
2^10 = 1024 [1023] 3x 341
2^11 = 2048 [2047]
2^12 = 4096 [4095]

misschien alleen bij de oneven machten >3 ?

ik zie wel een patroon bij de getallen die geen priemgetallen zijn. Het is iedere keer 3x X waarbij de volgende uitkomst X x4 +1 is
klopt ook niet helemaal want 511 is weer deelbaar door 7 (7x 73) en niet door drie. maar de deling door drie zorgt in ieder geval dat de even machten niet opgaan.
bij 2047 kun je weer door 23 delen. 4095 is deelbaar door 5.

//edit aanvulling met 'hogere machten'.


//edit2:
aan iedereen hieronder, ik deed het inderdaad fout. maar zoals o.a. freezexj zegt faalt het dan alsnog bij 11. ook bij 13 trouwens, 2^13=4192 en bij 4191 is de som van de getallen 15, dus deelbaar door 3.

[Reactie gewijzigd door SiC123 op 12 mei 2009 00:07]

Er staat ook als voorwaarde dat n een priemgetal is ;) 8 is geen priemgetal.., net als 4 en 6 dus.
Helaas faalt ook dat redelijk snel, bij 2^11-1 = 2047 faalt op 23x89 ...
Tot nu toe is er geen perfecte reeks ontdekt, die alleen maar priemgetallen voortbrengt. Leonhard Euler zat misschien wel het dichtste bij met n^2 + n + 41, wat voor de eerste 40 n een priemgetal ophoest.
Je doet het fout. Witte zegt: als n een priemgetal is dan is 2^n -1 ook een priemgetal. Vervolgens kom je met het voorbeeld n = 8; dan klopt het inderdaad niet, want 8 is gťťn priemgetal... Bij de voorbeelden in je rijtje waarbij n wťl een priemgetal is zie je dat het klopt:

2^2 - 1 = 3 (n = 2 is een priemgetal en 3 is een priemgetal)
2^3 - 1 = 7 (n = 3 is priem, 7 is priem)
2^5 - 1 = 31 (n = 5 is priem, 31 is priem)
2^7 - 1 = 127 (n = 7 is priem, 127 is priem)

Maar dit levert natuurlijk niet alle priemgetallen op, er zijn ook priemgetallen die niet aan de vorm 2^n - 1 voldoen.
Ik ben net met mn studie informatica gestopt omdat ik een hekel had aan polynomen, maar hier is als het goed is bewijs voor iig het omgekeerde:
http://primes.utm.edu/notes/proofs/Theorem2.html
Waarom gaat iedereen er hier vanuit dat deze ontdekking cryptografie in gevaar brengt? Dit is een specifiek patroon, dat je nog geen stap dichterbij factorisering brengt.
Moderne cryptografie is meestal gebaseerd op het feit dat je 2 priemgetallen wel snel met elkaar kunt vermenigvuldigen, maar daarna uit dat product nog maar met heel veel meer moeite de oorspronkelijke getallen terug kunt vinden. Bewijzen dat 7621553 niet priem is, is niet gek lastig (voor een computer). Proths Theorem kan je dat snel genoeg vertellen. Echter is het tot nu toe onmogelijk om zonder alle opties na te gaan, uit te zoeken wat precies die delers zijn. (Aan de hand daarvan kun je dan de rest doorrekenen, om uiteindelijk je boodschap te ontcijferen).
misschien stomme vraag, maar de lijst met priemgetallen is niet zo heel lang in vergelijking met alle getallen, beperk je dan niet heel erg de keuze als je je algoritme baseerd op 2 priemgetallen?
2 random getallen zou dan veel moeilijker te berekenen zijn, want daar zitten die priemgetallen ook tussen.
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 iOS 10 Google Pixel Apple iPhone 7 Sony PlayStation VR AMD Radeon RX 480 4GB Battlefield 1 Google Android Nougat Watch Dogs 2

© 1998 - 2016 de Persgroep Online Services B.V. Tweakers vormt samen met o.a. Autotrack en Carsom.nl de Persgroep Online Services B.V. Hosting door True