Indiërs ontwikkelen algoritme voor priemgetallen

Verwijderd schrijft dat drie Indiase geleerden een foolproof manier hebben gevonden om priemgetallen te identificeren. De manier waarop ze dat doen is weliswaar langzamer dan de huidige methodes, maar ook een stuk zekerder: namelijk absoluut. Dit in tegenstelling tot de huidige methoden, die nog altijd een kleine foutmarge hebben.

Voor zover bekend begon de Griekse wiskundige Eratosthenes rond het jaar 200 vChr. met het zoeken naar de foolproof manier om priemgetallen te identificeren. Destijds had hij één manier gevonden om uit te zoeken of een getal een priemgetal was. Sindsdien zijn er dus talloze methoden ontdekt, maar nu pas eentje die honderd procent zekerheid biedt. De voornaamste geleerde van de drie - Manindra Agrawal - had het volgende te zeggen over de ontdekking:

"Our algorithm is deterministic; it has no chance of committing any error," said Manindra Agrawal, the principal author of the formula. "Our first objective was to find a method that is foolproof. Now, I am sure other researchers, or may be some of us, will start asking how can the number of steps be cut down and make the computation faster."
"We have received several responses. All of them have expressed satisfaction with the new algorithm," Agrawal told The Associated Press by telephone. "No one has doubted our claim," he said. "We have used more steps than the current methods in use," explains Agrawal.

Reacties (148)

Crack 12 augustus 2002 12:55

Dit nieuws lijkt me niet zo wereldschokkend.
Dat zou wel anders geweest zijn, als deze methode veel sneller is, dan de reeds bekende algoritmen.
In dat geval blijken heel veel beveiligingen namelijk plotseling zo lek als een mandje.

Adion

@Crack • 12 augustus 2002 13:04

Ze zeggen dan ook dat ze nu verder op zoek gaan naar een sneller algoritme.

Dit algoritme is trouwens wel trager, maar wel 100% zeker.
Dus een ander algoritme moet misschien nadien nog bevestigd worden met nog een ander algoritme, wat in totaal misschien trager is dan 1 algoritme dat zekerheid bied.

apa @Adion • 12 augustus 2002 13:48

Dus een ander algoritme moet misschien nadien nog bevestigd worden met nog een ander algoritme, wat in totaal misschien trager is dan 1 algoritme dat zekerheid bied.

Neen... Momenteel werd een kandidaat-priemgetal getest met alle bekende algoritmen. Als het al de tests doorstond, dan kwam de ultieme test: domweg alle mogelijkheden testen. Er zijn zowieso delers die je kan schrappen; toch duurt het vaak nog een eeuwigheid om een kandidaat zo te testen. Als je 1 enkel algoritme hebt, dan is dat natuurlijk veel sneller dan alle vorige (snellere) algoritmen samen plus de full-test.

Ik vermoed trouwens dat ze deze test dan ook enkel zullen gebruiken als vervanging van de full-test. Je kan een kandidaat-priemgetal dan vaak vrij snel afwijzen doordat het een van die tests niet doorstaat.

RealCato 12 augustus 2002 13:15

Priemgetallen ontbinden is juist zo interessant omdat het zo lang duurt om ze te ontbinden.
Het is erg leuk dat er nu een methode is die met zekerheid kan bepalen of een getal een priemgetal is, maar dit algoritme is vast exponentieel van orde. Als nu iemand een polynomiaal algoritme vind om dit probleem op te lossen, maar het algoritme is niet helemaal zeker, dan kan dit toch interessant zijn aangezien computers hier heel goed mee kunnen omgaan.
In die zin is het dus ook interessant voor de wetenschap om benaderingsalgoritmes te bedenken, ondanks dat ze vaker onzekerheden hebben, zijn ze meestal erg snel.

Btw voor wie de nobelprijs wil winnen en goed is met priemgetallen:
http://www.claymath.org/prizeproblems/riemann.htm

Jit @RealCato • 12 augustus 2002 13:38

[Off-Topic] De Nobel-prijs voor de wiskunde bestaat niet. Nobels vrouw is er ooit met een wiskundige vandoor gegaan...
[/Off-Topic]

Verwijderd @Jit • 12 augustus 2002 19:32

Je kan altijd voor de Fields medaille gaan. Zowat de 'nobelprijs' voor wiskunde.

http://elib.zib.de/IMU/medals/
http://www-groups.dcs.st-and.ac.uk/~history/Societies/FieldsMedal.html

Verwijderd @RealCato • 12 augustus 2002 13:30

Priemgetallen kan je per definitie niet ontbinden, je bedoelt waarschijnlijk het zoeken van 2 priemgetallen als je alleen het gemeenschappelijke product hebt.

Verwijderd @Verwijderd • 12 augustus 2002 15:42

...maar je kunt ze wel proberen te ontbinden, als je nog niet weet of het een priemgetal is of niet.

mvdejong 12 augustus 2002 13:23

Priemgetallen zijn zeer belangrijk, juist nu.

Een aantal van de belangrijkste encryptie-algoritmen (waaronder bij. PGP) baseren zich op het gegeven dat het nog steeds bijzonder lang duurt om een getal dat het product is van 2 grote priem-getallen (enkele 10-tallen cijfers) in zijn factoren te ontbinden.

Hierbij ligt de basis van het vertrouwen in de wetenschap dat priem-getallen al een paar millennia enthousiast door wetenschappers en amateurs worden onderzocht, en het dus vrij onwaarschijnlijk is dat iemand een methode vindt om het ontbinden in factoren een paar orde's sneller te maken.

Zou iemand daar wel in slagen, dan is met een klap het grootste deel van de huidige security op het Internet weggevaagd, credit-card-nummers liggen open voor hackers, enz.

Diadem 12 augustus 2002 14:10

Voor zover bekend begon de Griekse wiskundige Eratosthenes rond het jaar 200 vChr. met het zoeken naar de foolproof manier om priemgetallen te identificeren. Destijds had hij één manier gevonden om uit te zoeken of een getal een priemgetal was. Sindsdien zijn er dus talloze methoden ontdekt, maar nu pas eentje die honderd procent zekerheid biedt.

Dit is niet waar. Het bedenken van een algoritme om alle priemgetallen te vinden kan iedereen. Simpelweg een getal delen door alle voorgaande getallen, en als het door geen van die getallen deelbaar is is het een priemgetal. Hierop verbeteren is ook heel makkelijk, maar daarop zal ik niet ingaan.

De truc is dat de allersnelste algoritmes niet alle priemgetallen vonden. De meeste wel, maar niet allemaal.

Dit huidige algoritme is bijzonder omdat het supersnel is (al is het ietsje langer dan de allersnelste) en wel alle priemgetallen vind.

Maar dat men dat tot nu toe niet kon is onzin.

Verwijderd @Diadem • 12 augustus 2002 21:27

Het bedenken van een algoritme om alle priemgetallen te vinden kan iedereen. Simpelweg een getal delen door alle voorgaande getallen

Je hoeft niet door alle getallen te delen. Wanneer je de delers van een getal x zoekt, hoef je alleen maar de getallen af te gaan die kleiner zijn dan de wortel van x, en dat scheelt al een stuk

Carnifex @Verwijderd • 12 augustus 2002 21:58

Ik vermoed dat diadem dat ook bedoelde met 'verbeteren'. Hij wil gewoon duidelijk te maken dat er een heel simpel algoritme bestaat dat ook al werkt, alleen minder snel is.

Diadem @Verwijderd • 12 augustus 2002 22:03

Natuurlijk. Dat snap ik ook wel. Ik gaf het simpelst mogelijke algoritme. Ik zei erachteraan ook niet voor niets 'Hierop verbeteren is ook heel makkelijk'.

Een relatief simpel en effectief algoritme gaat als volgt:

Neem getal x
Bereken de wortel op gehelen nauwkeurig. Noem deze y.
Deel x door alle priemgetallen tussen 2 en y.
Als x deelbaar is door geen van deze getallen is x een priemgetal.

De truuc van dit algoritme is dat elk getal te ontbinden is in priemfactoren - elk getal is te schrijven als een vermenivuldiging van alleen maar priemgetallen.

Wat je hiervoor wel moet doen is een lijst van priemgetallen bijhouden. Al hoeft dit geen complete lijst te zijn, om [b]alle[b] priemgetallen tot een miljoen te vinden moet je aan het begin een lijst bijhouden van alle priemgetallen tot 1000.

NB: Ik heb dit algoritme met een vriend ooit eens geschreven. Op een Pentium II 266 werd de snelheid gelimiteerd doordat hij binnen een fractie van een seconde het geheugen vol had en op de harde schijf verder moest

Verwijderd @Diadem • 13 augustus 2002 02:16

Natuurlijk, dit dit algo is simpeler dan de eerdere tests (tenminste die, die 100% zekerheid bieden).
Maar wat het ook zegt is dat het niet alleen simpeler is dan de huidige algo's, maar (voor de mensen die bekend zijn met complexiteitstheorie) dat het probleem blijkbaar in P (in polynomiale tijd oplosbaar) zit, en niet in NP (op een nondeterministische machine in polynomiale tijd oplosbaar). En dat is een vraag die al jaren beantwoord moest worden.
(huidige algo's waren of te langzaam (NP) of gaven antwoord op de verkeerde vraag (niet "is n priem", maar "is de kans dat n priem is kleiner dan x", met x>0)

Zarc.oh 12 augustus 2002 12:54

Zijn scriptie is te vinden op http://www.cse.iitk.ac.in/news/primality.pdf

Verwijderd @Zarc.oh • 12 augustus 2002 15:43

Oei! ik lees dat 'ie in de orde (log n)^12 ligt (bewezen), maar misschien richting (log n)^6... voor encryptie lijkt me dat nog veel te langzaam!
Stel: n is 100-cijferig, dan doet 'ie er een x*(10^24) aantal berekeningen over (x constant). Dat is *veel!*

edit:

Als 'ie in de buurt van (log n)^6 blijkt te liggen, ligt 't al wel binnen het bereik van huidige desktops, lijkt me.

Verwijderd @Verwijderd • 12 augustus 2002 16:14

Ik ben in al mijn nieuwsgierigheid naar de orde van het algoritme ook het artikel gaan doorspitten.

Het is echter niet O((log n)^12), maar O(t(n)poly(log t(n)))) [zie blz 2] met t(n)=(log n)^12, danwel (log n)^6 of eventueel (lo^g n)^3. Dat laatste is afhankelijk van 2 geloofwaardige hypothesen.
NB de functie poly wordt niet gespecificeerd. Maakt waarschijnlijk niet veel uit voor de interpretatie van de orde.

Kan iemand mij verder helpen en vertellen in welke orde van grootte dit algoritme ligt??
O(n), O(n log n), of toch O((log n)^12)

MetalStef

@Verwijderd • 13 augustus 2002 09:05

Is er ook een moderatie "+1 Het ziet er ongelooflijk interessant uit, maar ik begrijp er geen hol van"?

Verwijderd 12 augustus 2002 15:02

Wat bovenaan staat dat er nog geen foolproff manier was klopt niet helemaal de zeef van Eratoshenes zoals ook al in het artikel aangegeven is was de eerste maar ook direct de fool-proof manier

De zeef van Eratoshenes was volledig fool-proof maar had als enige grote nadeel dat de tijd die nodig was exponentieel toenam naarmate het priemgetal groter werd. Men begon het getal te delen door elk getal van 2 t/m de helft van het "priemgetal". Het enige voordeel wat deze manier heeft tov de zeef is dat deze sneller werkt en niet exponentieel toeneemt.

Het wordt pas een groot gevaar wanneer iemand een manier vind om priemgetallen te ontbinden in factoren. Dat zou een betekenen dat de cryptografie van oa RSA helemaal niet meer goed zou zijn.

edit:

foutje da's waar maar volgens mij wordt het een probleem als iemand een formule vind om razendsnel grote priemgetallen te maken, het ontbinden in factoren dat is nou net het probleem waarom het ontcijferen van encryptie zo moeilijk maakt

Major 7 @Verwijderd • 12 augustus 2002 15:15

.... priemgetallen te ontbinden in factoren...

Dan ben je snel klaar

: het priemgetal zelf en het getal 1.

RemcoX @Verwijderd • 12 augustus 2002 16:39

Het gaat bij die beveiliging om een niet-priemgetal, dat moet worden ontbonden in 2 grote priemgetallen.

Verwijderd 12 augustus 2002 13:10

1. Wetenschappers mogen zeker met foutenmarges werken, dat is vaak een snelle en goedkope manier om na te gaan of je een resultaat mag verwijderen.

Een toepassing van dat algoritme zou bijvoorbeeld kunnen zijn dat ze eerst een snel algoritme laten checken op priemgetallen, zodat je nog maar een kleine verzameling overhoudt van mogelijke kandidaten, en dan dit nieuwe algoritme gebruiken om met 100% zekerheid te kunnen zeggen dat het priemgetallen zijn.

2. De huidige beveiling is niet gebaseerd op het vinden van priemgetallen, maar op het opdelen van een getal in zijn priemgetallen. De snelheid van dit soort algoritmes is dan ook geen enkele bedreiging voor de veiligheid van vele bedrijven

Verwijderd 12 augustus 2002 12:46

wiskundig gezien zeer interessant. maar wat zijn de bruiksmogelijkheden van priemgetallen?

en weer te laat

McFizban @Verwijderd • 12 augustus 2002 12:48

Ze worden veel gebruikt in public key encryptie algoritmes.
Heel simpel gezegd: men neme twee hele grote priemgetallen: je geheime sleutel.
Vermenigvuldig ze met elkaar: je publieke sleutel.
Een bericht wordt versleuteld met je publieke sleutel. Alleen jij kan hem weer decoderen omdat alleen jij het bericht kan ontbinden m.b.v. je geheime sleutel.
Als je de geheime sleutel niet hebt, kun je ook achter het bericht komen. Je moet dan alleen de publieke sleutel ontbinden. Dit is echter heel tijdrovend, omdat de getallen zo groot zijn.
Heb je echter een geheim sleutelpaar gemaakt dat geen echt priemgetel bevat (een van de getallen kan ontbonden worden) dan is het vinden van de geheime sleutel een stuk makkelelijker.
Daarom is het voor de veiligheid belangrijk dat je zeker weet dat je twee goede priemgetallen maakt.

zork @McFizban • 12 augustus 2002 15:03

RSA is a public-key cryptosystem for both encryption and authentication; it was invented in 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman. It works as follows: take two large primes, p and q, and find their product n=pq; n is called the modulus. Choose a number, e, less than n and relatively prime to (p-1)(q-1), which means that e and (p-1)(q-1) have no common factors except 1. Find another number d such that (ed - 1) is divisible by (p-1)(q-1). The values e and d are called the public and private exponents, respectively. The public key is the pair (n,e); the private key is (n,d). The factors p and q maybe kept with the private key, or destroyed.
RSA privacy encryption: Suppose Alice wants to send a message m to Bob. Alice creates the ciphertext c by exponentiating: c=me mod n,
where e and n are Bob?s public key. She sends c to Bob. To decrypt, Bob also exponentiates: m=cd mod n; the relationship between e
and d ensures that Bob correctly recovers m. Since only Bob knows d, only Bob can decrypt.

Een kort artikeltje over de werking van het Public Key Cryptosystem RSA.

Het RSA Algoritme werkt als volgt:

- Neem twee grote priemgetallen, p en q, en bereken hun product m = p * q.
- Kies een getal, e, kleiner dan m en relatieve priem tot (p-1)(q-1). Dit betekend dat e en
(p-1)(q-1) geen gemeenschappelijke delers behalve 1 hebben.
- Neem een ander getal, d, zo dat e * d ß 1 mod n
De getallen e en d worden de public en private componenten genoemd. De public key is het getallenpaar (n,e). De private key is (n,d). De factoren p en q heb je in principe niet meer nodig, dus kunnen met de private key bewaard worden of simpelweg vernietigd worden.

Voorbeeld:

Corry wil een geheime liefdesbrief sturen naar Nieky. Corry maakt de ciphertext c door de volgende formule: c=me mod n. Het getallenpaar(e,n) is Niekyfs public key. Corry stuurt c naar Nieky. Om de ciphertext te decrypten, voert Nieky de volgende berekening uit: m=cd mod n. De relatie tussen e en d verzekerd Nieky dat ze m correct uitleest. Aangezien zij de enige persoon is die d kent, is zij de enige die kan decrypten.

Dus de publieke sleutel (e) is niet p * q, maar een getal dat relatieve priem van (p-1)(q-1) is, en kleiner dan het product van beide priemgetallen. Dit betekend dat e en (p-1)(q-1) geen gemeenschappelijke delers behalve 1 hebben.

Voor Wiskunde B heb ik afgelopen schooljaar een practische opdracht over dergelijke public key cryptosystems gemaakt samen met een andere Tweaker. Inclusief software voor de GR om de benodigde berekeningen uit te voeren, en een compleet software pakket in C++ om te encrypten en te decrypten.

Verwijderd @zork • 12 augustus 2002 16:17

hey zork,

zou ik dat po tje voor wiskunde eens kunnen bekijken (online of via meel?)... vind het namenlijk we een interrestant onderwerp..

alvast bedankt...

bamboe @McFizban • 13 augustus 2002 08:47

Wie ligt er eigenlijk aan kop met het grootste priemgetal?
maar ja waarschijnlijk zullen ze dat toch geheim houden, ik vraag me af wat banken betalen voor het verkrijgen van priemgetallen, gezien ook de gehele pincode beveiliging er op berust.

/edit: met zoeken kwam ik deze website tegen, wel leuk: http://www.utm.edu/research/primes/

Verwijderd @bamboe • 19 augustus 2002 01:27

Het zoeken naar het grootste priemgetal is loos, er zijn namelijk oneindig veel priemgetallen. Mooi bewijs (door contradictie):

Stel er is een getal X wat het grootste priemgetal is.

Neem nu X! (X faculteit) en tel daar 1 bij op. X!+1 is niet deelbaar door alle n<X,n>1 (vanwege die +1) dus is OF X!+1 zelf een priemgetal (en X!+1 is > X), OF er is een getal Y, X<Y<X!+1 waar X!+1 door te delen is, wat zelf priem is (en Y>X).

Kortom, er is voor ieder priemgetal een groter priemgetal te vinden, dus er zijn oneidig veel priemgetallen.

Er zijn zelfs evenveel priemgetallen als natuurlijke getallen. Rara hoe kan dat.

Verwijderd @bamboe • 19 augustus 2002 01:57

Hardstikke leuk allemaal maar ik geloof niet in oneindigheid,als iets een begin heeft dan heeft het ook een einde.Anders zou de aantal positieve getallen even groot zijn als het aantal positieve + negatieve getallen.

Verwijderd @Verwijderd • 12 augustus 2002 12:48

Voor encryptie en CRC bijvoorbeeld

edit:
argh...te laat

Nahja, beter 2 zielen 1 gedachte dan een losse flodder.

Verwijderd @Verwijderd • 12 augustus 2002 15:08

offtopic:
Beetje flauw dat ze je dan een dubbelpost geven, bericht is in dezelfde minuut geplaatst als je voorganger. Sorry, ik mag dit bericht niet modereren

Kurgan @Verwijderd • 12 augustus 2002 15:50

Ja, er schijnen hier een aantal mensen rond te hangen die er plezier in hebben om anderen omlaag te modden door te strooien met dubbelposts, trolls en flamebaits. Zeker niets beters te doen of zo.

edit:
Kijk, dat bedoel ik nou. Zeg even iets iets wat enigszins uit de toon valt en je krijgt gelijk dingen als "overgewaardeerd" en "off-topic" naar je hoofd geslingerd.

Jongens, als je geen afwijkende mening kan verdragen moet je jezelf maar ergens afzonderen en vooral niet op internet gaan.

Zo, nu weer on-topic: weet iemand ergens te vinden HOE ze dat nu precies gedaan hebben? Ik kan ook wel een manier verzinnen die 100% zeker is. Je neemt een getal en kijkt of je het bij deling door een kleiner getal een geheel antwoord krijgt. Als je bij 1 begint en doorgaat totdat je alle getallen die kleiner zijn dan jouw getal hebt gehad, weet je 100% zeker dat het een priemgetal is. Ik neem aan dat ze het niet zo hebben aangepakt, anders was het geen nieuwsposting waard.

spasieba @Verwijderd • 12 augustus 2002 17:20

Je hoeft niet alle getallen na te gaan die kleiner zijn dan het te checken getal.

je hoeft maar van 2 tot en met de afgeronde wortel van het te checken getal te gaan.

( trouwens die wortel mag natuurlijk ook geen reeel getal zijn he

)

edit:

dit was een reactie op kurgan.

crisp Senior Developer @Verwijderd • 12 augustus 2002 17:42

Sterker nog, om te bewijzen dat getal n priem is hoef je alleen maar te checken op deelbaarheid met alle priemgetallen tot wortel n.
Dus om te kijken of bijvoorbeeld 113 priem is check je alleen of je het kan delen door 2, 3, 5, en 7 (wortel 113 = 10,63 dus 11 hoef je al niet meer te proberen).

komkommer @Verwijderd • 12 augustus 2002 22:33

ja, maar het is een algoritme, dus geen prog

Verwijderd @Verwijderd • 12 augustus 2002 16:00

ik zie sowieso het nut van dat modereren niet zo in, en iig al helemaal niet om me er druk om te maken

zork @Verwijderd • 12 augustus 2002 18:51

Door gericht te modereren, wordt de waarde van een nieuwsbericht verhoogt. Hoe dan? Nou, als iemand met onzin, flames of ander onzinige reacties in het draadje gaat gooien, wordt het omlaag gemodereerd. Hierdoor worden deze reacties op een lager niveau gebracht, waardoor ze voor veel mensen uit het draadje wegvallen. Zo blijven alleen de informatieve en nuttige reacties over. Zonder modereren heeft reageren geen zin in mijn ogen, omdat het dan waarschijnlijk een moddergooiende chatbox wordt. Ik haal bij de meeste nieuwsberichten een groot deel van de content uit de erbij horende draadjes!

Kurgan @Verwijderd • 13 augustus 2002 00:15

Daar heb je wel gelijk in zork, maar de laatste tijd worden ook normale berichten al heel snel omlaag gemod. Als je geen afwijkende mening mag verkondigen wat is het nut van dit hele forum dan, ik ga toch ook niet elke post die me niet bevalt als flamebait modden? Op die manier verziek je het forum ook in een noodtempo, en wordt het modsysteem een soort terreurmiddel i.pv. een ordehandhavingsmiddel. Als je nou nog kon zien door wie je omlaag gemod wordt, dan zouden die wannabe-admins ook verantwoordelijk kunnen worden gehouden voor hun gedrag, nu is het allemaal zo eenzijdig.

E-jey 12 augustus 2002 12:48

IK heb het wel ooit gehoord wat een priem getal was maar ik ben het weer vergeten

Liqued @E-jey • 12 augustus 2002 12:51

Priemgetal is een getal dat je alleen door 1 of zichzelf kan delen (zoals bv 7)

edit:
typo tnx wildhagen

wildhagen

@Liqued • 12 augustus 2002 12:52

Priemgetal is een getal dat je alleen door 2 of zichzelf kan delen (zoals bv 7)

Je bedoelt door 1 en zichzelf? 7 delen door 2 gaat niet lukken, terwijl 7 wel een priemgetal is...

Verwijderd @Liqued • 12 augustus 2002 12:52

7 / 2 = ?

DUTCHSPiRiT @Verwijderd • 12 augustus 2002 12:57

3.5

Ruuddie @Verwijderd • 12 augustus 2002 13:24

LOL het moet wel op een heel getal uit komen he, thus zonder iets achter de komma

Verwijderd @Verwijderd • 12 augustus 2002 15:22

dank je wel, ik kon er even niet opkomen

(reactie op dutchspirit)

Verwijderd @Liqued • 12 augustus 2002 13:48

En waarbij de uitkomst een natuurlijk getal is.

Verwijderd @E-jey • 12 augustus 2002 12:53

Priemgetallen zijn getallen die je alleen door zichzelf en 1 kan delen. En de reden dat ze belangrijk voor encryptie is omdat je ze dus niet kan ontbinden in factoren.

Ruuddie @E-jey • 12 augustus 2002 12:52

Een getal wat alleen door 1 of zichzelf te delen is, zoals 13