Wat zijn de gevolgen als men......

[TutanRamon]

......een soort functie bedenkt waarmee je elk priemgetal kunt berekenen? Want volgens mij zijn een heleboel (de)codeersystemen gebaseerd op de 'geheimen' van priemgetallen, bijvoorbeeld bankpasjes. Die worden gecontroleerd op echtheid door ingewikkelde berekeningen met priemgetallen. Maar wat zou er gebeuren als men een functie ontwikkeld (net zoiets als F(n)=2^(2^n)) ??

Of is er nix aan de hand en kunnen we eindelijk het vermoeden van Goldbach bewijzen?

[Ivo]

Volgens mij kan dat niet, want de priemgetallen liggen niet op een lijn van een grafiek met welke exponent dan ook.

[TutanRamon]

weet ik, maar "stel"....

[Verwijderd]

Als je die functie ooit zou kunnen vinden, wordt cryptografie weer een beetje moeilijker... Maar aangezien het zeer onzeker is of die functie wel bestaat, lijkt het me voorlopig niet zo'n probleem.

[joepP]

Op vrijdag 12 oktober 2001 17:32 schreef TutanRamon het volgende:
......een soort functie bedenkt waarmee je elk priemgetal kunt berekenen? Want volgens mij zijn een heleboel (de)codeersystemen gebaseerd op de 'geheimen' van priemgetallen, bijvoorbeeld bankpasjes. Die worden gecontroleerd op echtheid door ingewikkelde berekeningen met priemgetallen. Maar wat zou er gebeuren als men een functie ontwikkeld (net zoiets als F(n)=2^(2^n)) ??

Of is er nix aan de hand en kunnen we eindelijk het vermoeden van Goldbach bewijzen?

Je bedoelt PGP, dat gebaseerd is op de relatieve eenvoud van het vinden van grote priemgetallen, A en B, en de belachelijke moeite die het kost een getal C (=A*B) in zijn priemfactoren te ontbinden..

[TutanRamon]

Op vrijdag 12 oktober 2001 17:57 schreef joepP het volgende:

[..]

Je bedoelt PGP, dat gebaseerd is op de relatieve eenvoud van het vinden van grote priemgetallen, A en B, en de belachelijke moeite die het kost een getal C (=A*B) in zijn priemfactoren te ontbinden..

Kan jij daar eens een voorbeeld van geven want ik ben nog niet echt bekend met de wereld van priem.

[Verwijderd]

PGP (RSA):
twee grote priem getallen: a, b
c = (a * b)

x = c mod y (kies y bereken x)

x is een groot getal en je privat key, y is je public key en een stuk kleiner.

coderen: B mod y = E
decoderen: E mod x = B

dat is het gellof ik. als je snel priemgetallen kunt berekenen, kun je dus heel snel het bron getal c bepalen (nou ja...) en dan heb je dus een eerste stap gezet in het kraken. Maar dat kan niet (nog?)

[Lord Daemon]

Er bestaat geen functie die alle priemgetallen genereert. Een priemgetal heeft op zich natuurlijk erg weinig met de vorige priemgetallen te maken, dus lijkt het me nogal onlogisch te denken dat er een functie bestaat die uit kleine priemgetallen grote priemgetallen genereert. Misschien kan iemand iwskundig bewijzen dat zo een functie niet kan bestaan?

(Ik neem overigens aan dat we het hier over een discrete functie hebben?)

[Verwijderd]

hmm, wat was dat ook al weer
ik herinner me iets van (2^priemgetal ) en + of - 1

[Chemist]

Poeh , een functie ...
Het zal iets worden in de trend van:
(x/y) [geen element van]N
voor iedere
y [element] N
en
y < x.

(is dit eigenlijk wel een functie ??)

[Confusion]

Volgens mij bestaat die functie al en is het de Riemann zeta functie.

[Chemist]

Inderdaad !!
Niet helemaal doorgelezen, maar hier staat daar meer over ..

[Verwijderd]

Op vrijdag 12 oktober 2001 19:08 schreef Lord Daemon het volgende:
Er bestaat geen functie die alle priemgetallen genereert. Een priemgetal heeft op zich natuurlijk erg weinig met de vorige priemgetallen te maken, dus lijkt het me nogal onlogisch te denken dat er een functie bestaat die uit kleine priemgetallen grote priemgetallen genereert. Misschien kan iemand iwskundig bewijzen dat zo een functie niet kan bestaan?

(Ik neem overigens aan dat we het hier over een discrete functie hebben?)

Wat hier denk ik bedoeld wordt, is een programma dat bij een gegeven getal snel zegt of het een priemgetal is.

Wat nog een onbewezen probleem is, is of er een programma bestaat dat getallen kan testen op priem-heid in een aantal stapjes dat polynomiaal afhangt van de lengte van het getal.

Dus zoiets van jij geeft een getal van n cijfers, en de computer geeft je in 87*n^3+56*n^2+19 (of een ander polynoom) stapjes het antwoord of dit getal wel of niet priem is en als je een beetje bikkel bent, maak je een programma dat je, als het getal niet priem is, de factorisatie geeft (dit is nog een stukje moeilijker).

De gevolgen:

Cryptografiesystemen zijn erop gebaseerd dat men grote getallen niet snel kan factoriseren, dus als je dat wel kan, kan je gecodeerde berichten ontcijferen en als je kwaad wil, dan zeg je: kom maar op met jullie pin-codes, wachtwoorden, creditcard nummers etc.

Als factorisatie van priemgetallen lukt in polynomiale tijd, dan lukken een hoop andere problemen ook ineens in polynomiale tijd. Ik weet even geen voorbeelden, maar het zou zomaar kunnen dat het handelsreizigersprobleem of zoiets opgelost wordt.

Het schijnt dat quantumcomputers (die nu alleen nog maar in theorie bestaan) in staat zijn om dit probleem op te lossen, maar als we die eenmaal gemaakt hebben, dan is heeft de cryptografie meteen een antwoord, want het schijnt dat je met quantumcomputers "perfect secrecy" kan bereiken. (De droom van alle cryptografen, die ze meteen allemaal werkeloos maakt )

[FCA]

Er is geen functie bekend die alleen maar priemgetallen oplevert. (behalve constante functies dan )

Een functie die extreem veel priemgetallen oplevert
is bijvoorbeeld x^2 + x + 41 voor x gehele getallen. Dit gaat natuurlijk fout als x = 41. Maar tot en met x=39 zijn het allemaal priemgetallen, en ook na 41 zitten er een hoop priemgetallen bij.

Waarom? Omdat Exp(Pi*Sqrt(163)) bijna gelijk aan een geheel getal is, en 163 op een of andere manier met 41 kan worden geschreven (heb het boek waar ik het uit heb niet bij de hand)

Wilde gok:
Dus als je een geheel getal y zou kunnen vinden die waarvoor geldt exp(Pi*Sqrt(y))=geheel getal, dan zou je een functie kunnen vinden die alleen maar priemgetallen oplevert. Omdat e en Pi transcedent zijn, lijkt mij dit erg onwaarschijnlijk (hoewel het volgens mij nog niet bewezen is dat het niet kan). En dan nog heb je geen functie die alle priemgetallen oplevert.