[wiskunde]waarom zijn priemgetallen zo belangrijk?

[Paultje3181]

Waarom zijn priemgetallen zo belangrijk in cryptologie? Mij lijkt het namelijk logisch dat hoe meer getallen, hoe moeilijker te kraken. Bijvoorbeeld: je test alle priemgetallen en de rest kun je afstrepen. Dit is een extra actie en duurt dus langer. Waarom zijn priemgetallen dan juist zo belangrijk? Of mis ik een puntje???

[Erkens]

ga eens na wat precies priemgetallen zijn

[brokenp]

check
ftp://ftp.rsasecurity.com...gorithm/rsa-oaep_spec.pdf
Kijk maar eens of je dat begrijpt.
Dan snap je waarom ze daar priems voor gebruiken RSA.
Het heeft er natuurlijk mee te maken dat priem getallen ondeelbaar zijn.

[TD-er]

In de cryptografie worden grote getallen gebruikt om data te versleutelen.
Hoe groter het getal hoe kleiner de kans dat men perongeluk het juiste getal gebruikt om het te decrypten.

Even kort door de bocht...
Die grote sleutels zijn het product van 2 priemgetallen. Als je die 2 getallen met elkaar vermenigvuldigd krijg je de uiteindelijke sleutel.
Het ontbinden van de sleutel in zijn oorspronkelijke getallen gaat een stuk lastiger als het priemgetallen zijn. Er is namelijk geen formule om "het volgende" priemgetal te berekenen als je er een hebt. Voor het volgende even getal is dat er bijvoorbeeld wel. Je zult dus alle mogelijkheden moeten uitsluiten, wat dus zoveel rekenwerk met zich meebrengt dat het vrijwel onmogelijk is om het snel te kraken.

Verder hebben priemgetallen nogal wat leuke eigenschappen.

[cwppol]

Dit is nou een typisch voorbeeld van een leuk onderwerp... Van die dingen die je altijd al wou eten, maar nog nooit op het idee gekomen was om het op te zoeken! Bedankt heren (?) voor het duidelijke antwoord. Nu nog even flink studeren op die pdf om de betekenis te doorgronden!

[Anoniem: 10445]

Zoek in de bieb eens naar :

Pasjes en Pincodes // van de Craats // Aramith

[brokenp]

IK zie dat ik je een link heb gegeven naar een pdf je over een speciaal type rsa versleuteling, lees appendix B eerst, daarin staat de wiskundige achtergrond.
Als deze pdf onduidelijk is, gewoon zoeken op rsa.com op algorithm

[Paultje3181]

ik weet wel wat priemgetallen zijn en ook al de bijzondere eigenschappen. maar waarom juist priemgetallen voor codering? En mijn redering geld toch wel voor brute force??? Maar ik ga ff die pdf lezen... THNX

Maarrre, mijn engels is niet zo super....

[ Voor 12% gewijzigd door Paultje3181 op 13-04-2003 17:02 ]

[Anoniem: 63393]

Paultje3181 schreef op 13 April 2003 @ 16:53:
ik weet wel wat priemgetallen zijn en ook al de bijzondere eigenschappen. maar waarom juist priemgetallen voor codering? En mijn redering geld toch wel voor brute force??? Maar ik ga ff die pdf lezen... THNX

Maarrre, mijn engels is niet zo super....

Zie: http://www.win.tue.nl/~jessers/aansluiting/rsageheim.htm, onderaan bij "studiemateriaal". Moet lukken, met een beetje inspanning.

[Anoniem: 66444]

Ben ik nou dom of is krijg je een meer random getal als ze die dingen zelf verzinnen? Even rossen op je keypad?

Domme vraag.. sorry niks gezegt, ik heb net het stukje gelezen over die brief.. word ineens veeeel duidelijk

EDIT, JP moet veeeeeeeel beter gaan lezen *shame on me!*

[ Voor 45% gewijzigd door Anoniem: 66444 op 13-04-2003 17:48 . Reden: Oef, beter lezen ]

[Anoniem: 14124]

Ik denk dat er een hoop mensen zijn die niet eens weten wat priemgetallen zijn, dus wellicht is het leuk om daar ook wat over uit te leggen.

[Paultje3181]

Een priemgetal is een geheel getal n>1 met als enige deler het getal 1, en zichzelf.
Een priemgetal heeft dus 2 delers zichzelf en 1.
Het getal 1 is een uitzondering want een priemgetal heeft precies 2 delers 1 heeft er maar één.

zie google: priemgetallen

[ Voor 8% gewijzigd door Paultje3181 op 13-04-2003 18:01 ]

[Anoniem: 29769]

ik weet niet meer hoe het precies zat maar er staat me iets van het volgende bij. Je heb twee priem getallen nodig p en q. Het product van deze twee is openbaar en kan gebruikt worden om gegevens te coderen. Om dit weer ongedaan te maken moet je p en q afzonderlijk weten. Als je deze niet weet moet je deze gaan gokken (bruteforce). Als p en q priemgetallen zijn is er maar één juiste combinatie. Als je geen priemgetallen zou nemen zou je wel eens nog meer waarden kunnen vinden die samen hetzelfde product vormen als pq. Dus door voor p en q priemgetallen te nemen duurt het langer om te bruteforcen.

Ik weet niet of ik het goed heb dus correct me if i am wrong

[windancer]

albert_gerritsen heeft het bij het rechte eind.

Bij het versleutelen wil je een operatie gebruiken die de ene kant op (encyptie) weinig moeite kost maar de ander kant op (decryptie) veel moeite kost, tenzij je meer informatie hebt. Van een aantal priemfactoren het product nemen kost weinig werk (gewoon vermenigvuldigen) maar om een getal te ontbinden in priemfactoren kost veel moeite, tenzij je (1 van) de getallen al kent.

[snoopy]

Precies, heb hier thuis ergens een boek liggen waar je een paar voorbeelden in staan over dit (en andersoortige) encryptie.

Voor de liefhebbers hieronder de gegevens van dit boek:
Titel: Code (oorspronkelijke engelse titel: The Code Book)
Auteur: Simon Singh
ISBN: 90 295 3743 4

[Paultje3181]

thnx das idd de oplossing die ik zocht

[Denker]

Wij hebben voor het vak wiskunde een profielwerkstuk gemaakt over cryptografie. Het resultaat staat op internet: http://www.cryptonet.tk

Ook een stukje over priemgetallen,

Een berichtje in het gastenboek stellen we op prijs.

En het boek van Simon is leuk ja, heb 'm nog niet helemaal uit.

[ Voor 13% gewijzigd door Denker op 13-04-2003 19:45 ]

[Knutselsmurf]

Paultje3181 schreef op 13 April 2003 @ 18:00:
Een priemgetal is een geheel getal n>1 met als enige deler het getal 1, en zichzelf.
Een priemgetal heeft dus 2 delers zichzelf en 1.
Het getal 1 is een uitzondering want een priemgetal heeft precies 2 delers 1 heeft er maar één.

zie google: priemgetallen

Volgens sommige bronnen is 1 geen priemgetal, om de volgende reden:
Ieder getal kun je maar op 1 manier schrijven als het product van 1 of meer priemgetallen. Bijvoorbeeld 15=5*3 en 36=2*2*3*3
Bijvoorbeeld eerder genoemd encryptiealgoritme is hierop gebaseerd. het product pq van 2 priemgetallen p en q is op geen enkele andere wijze te ontleden. Als 1 een priemgetal zou zijn, zou bovenstaande stelling niet meer kloppen.

[marteltor]

Denker schreef op 13 april 2003 @ 19:42:
Wij hebben voor het vak wiskunde een profielwerkstuk gemaakt over cryptografie. Het resultaat staat op internet: http://www.cryptonet.tk

Ook een stukje over priemgetallen,

Een berichtje in het gastenboek stellen we op prijs.

En het boek van Simon is leuk ja, heb 'm nog niet helemaal uit.

had dat eerder verteld! ik heb het samen met paitor ook gemaakt! voor wiskunde en geschiedenis: www.encryptie.tk

[ Voor 3% gewijzigd door marteltor op 13-04-2003 20:25 ]

[Paultje3181]

Nog ff over die priemgetallen, volgens de definitie die ik geef is 1 ook geen priemgetal: n>1 namelijk... Maar logisch gezien natuurlijk wel.

[cwppol]

Klopt mijn aanname dat alle priemgetallen oneven zijn? Immers: anders zouden ze deelbaar zijn door 2. Bij het zoeken naar priemgetallen zou dan al de helft van de getallen afvallen (scheelt weer wat uren bruteforcen)

[Anoniem: 3057]

cwppol schreef op 15 april 2003 @ 18:31:
Klopt mijn aanname dat alle priemgetallen oneven zijn? Immers: anders zouden ze deelbaar zijn door 2. Bij het zoeken naar priemgetallen zou dan al de helft van de getallen afvallen (scheelt weer wat uren bruteforcen)

Er is 1 even priemgetal, nl. 2 zelf, maar verder zijn alle priemgetallen idd oneven.

Edit:
Een pagina met implementaties van een algoritme voor het vinden 'kleine' priemgetallen is hier te vinden: http://primes.utm.edu/lin...s/Eratosthenes/index.html
Meer info over priemgetallen op de startpagina van deze site: http://www.utm.edu/research/primes/

Enjoy

[ Voor 27% gewijzigd door Anoniem: 3057 op 15-04-2003 19:06 ]

[Anoniem: 11461]

cwppol schreef op 15 april 2003 @ 18:31:
Klopt mijn aanname dat alle priemgetallen oneven zijn? Immers: anders zouden ze deelbaar zijn door 2. Bij het zoeken naar priemgetallen zou dan al de helft van de getallen afvallen (scheelt weer wat uren bruteforcen)

Jep klopt precies wat je zegt. Neem aan dat het ook wel gebeurd en dat ze zo slim zijn om alleen oneven getallen te gaan bruteforcen.

[MrScratch]

Klopt mijn aanname dat alle priemgetallen oneven zijn? Immers: anders zouden ze deelbaar zijn door 2.

Allemaal, maar op 1 na dan natuurlijk. 2 zelf dus.

[tomato]

Anoniem: 11461 schreef op 15 April 2003 @ 18:41:
Jep klopt precies wat je zegt. Neem aan dat het ook wel gebeurd en dat ze zo slim zijn om alleen oneven getallen te gaan bruteforcen.

Dit is min of meer ook het principe achter de beroemde Zeef van Eratosthenes. Dit is een algoritme om alle priemgetallen kleiner of gelijk aan n te berekenen.

Daarbij slaan we niet alleen de even getallen over, maar ook alle getallen deelbaar door 3, door 5, door 7, etc. Alle veelvouden van priemgetallen slaan we dus over (waarna je alleen maar priemgetallen over houdt).

Het algoritme gaat als volgt:

1) Maak een gesorteerde lijst van alle positieve getallen kleiner of gelijk aan n.

2) Beginnend bij het getal 2, voeren we stap 3 uit.

3) Bekijk het huidige getal uit de lijst. Verwijder nu alle veelvouden van dit getal uit de lijst.

4) Ga verder naar het volgende (hogere) getal uit de lijst en voer stap 3 uit. Dit herhalen we steeds weer, tot het huidige getal groter is dan wortel(n).

We hebben nu een lijst met alle priemgetallen.

edit:
Typo gefixed, thanks ArCadE

[ Voor 3% gewijzigd door tomato op 16-04-2003 16:16 ]

[Anoniem: 3057]

tomato schreef op 15 April 2003 @ 19:15:
[...]

Dat zeg ik: GAMMA!

Een pagina met implementaties van een algoritme voor het vinden 'kleine' priemgetallen is hier te vinden: http://primes.utm.edu/lin...s/Eratosthenes/index.html

[tomato]

Anoniem: 3057 schreef op 15 April 2003 @ 19:36:
Dat zeg ik: GAMMA!

Ik legde het natuurlijk nog even uit voor diegenen die niet goed met de Engelse taal overweg kunnen

[Denker]

tomato schreef op 15 april 2003 @ 19:15:
[...]

Dit is min of meer ook het principe achter de beroemde Zeef van Eratosthenes. Dit is een algoritme om alle priemgetallen kleiner of gelijk aan n te berekenen.

Daarbij slaan we niet alleen de oneven getallen over, maar ook alle getallen deelbaar door 3, door 5, door 7, etc. Alle veelvouden van priemgetallen slaan we dus over (waarna je alleen maar priemgetallen over houdt).

Het algoritme gaat als volgt:

1) Maak een gesorteerde lijst van alle positieve getallen kleiner of gelijk aan n.

2) Beginnend bij het getal 2, voeren we stap 3 uit.

3) Bekijk het huidige getal uit de lijst. Verwijder nu alle veelvouden van dit getal uit de lijst.

4) Ga verder naar het volgende (hogere) getal uit de lijst en voer stap 3 uit. Dit herhalen we steeds weer, tot het huidige getal groter is dan wortel(n).

We hebben nu een lijst met alle priemgetallen.

Op onze website staat ook een voorbeeld van deze zeef. In het Nederlands!

[Glimi]

tomato schreef op 15 April 2003 @ 19:15:
Dit is min of meer ook het principe achter de beroemde Zeef van Eratosthenes. Dit is een algoritme om alle priemgetallen kleiner of gelijk aan n te berekenen.

Hoe mooi laat dit algoritme zich uitdrukken in een functionele taal:

code:

priemgetallen :: [Int]
priemgetallen = map head (iterate divideByDivider [2..])
                where divideByDivider (x:xs) = filter (\var -> var `rem` x /= 0) xs

Uit de reader FP van Jeroen Fokker

[KillR-B]

Glimi schreef op 15 April 2003 @ 22:38:
[...]


Hoe mooi laat dit algoritme zich uitdrukken in een functionele taal:

code:

priemgetallen :: [Int]
priemgetallen = map head (iterate divideByDivider [2..])
                where divideByDivider (x:xs) = filter (\var -> var `rem` x /= 0) xs

Uit de reader FP van Jeroen Fokker

Mmm, dit doet me erg denken aan de programmeertaal Clean. Een mooie taal overigens...

[Glimi]

KillR-B schreef op 16 April 2003 @ 00:39:
Mmm, dit doet me erg denken aan de programmeertaal Clean. Een mooie taal overigens...

offtopic:
Clean, Miranda, ML, Haskell, Stratego ; ze lijken ongeveer allemaal op elkaar als de meeste imperatieve talen op C lijken
Groot verschil tussen sommigen is echter dat sommige talen (Haskell like weet ik het zeker) puur zijn. Anderen hebben consessies gedaan richting imperatieve talen voor bijv IO

[ArCadE]

[quote]tomato schreef op 15 april 2003 @ 19:15:
[...]

Dit is min of meer ook het principe achter de beroemde Zeef van Eratosthenes. Dit is een algoritme om alle priemgetallen kleiner of gelijk aan n te berekenen.

oneven getallen over, maar ook alle getallen
^^^^^

Moet dit niet zijn: alle EVEN getallen??

[Anoniem: 50813]

Om even terug te komen op de originele vraag:
Hebben priemgetallen nog een ander doel naast encryptie?

[.oisyn]

Ja, bijvoorbeeld om te sturen naar een andere planeet, aangezien priemgetallen altijd priemgetallen zijn, in welk talstelsel je ze ook representeert

^{(Contact onlangs nog gezien? )}