b'\n_START_ARTICLE_\nPollards rho-algoritme\n_START_PARAGRAPH_\nPollards rho-algoritme is een algoritme dat door John Pollard in 1978 beschreven werd om de discrete logaritme zoals dat is gedefinieerd in een cyclische groep te berekenen. Het grote voordeel ten opzichte van het Baby-steps giant-steps-algoritme is dat voor deze methode geen opslagruimte nodig is.\n_START_SECTION_\nInleiding\n_START_PARAGRAPH_\nLaat G een groep zijn, met orde p, en G cyclisch. Laat g \\in G voortbrenger zijn van G en h \\in G. De discrete logaritme luidt nu als volgt: Bepaal de oplossing van g^{n}=h._NEWLINE_Pollards rho-algoritme definieert eerst een pseudowillekeurige reeks (opeenvolging) van elementen van een groep en kijkt dan naar een cyclus (kringloop) die in deze reeks voorkomt._NEWLINE_Deze groep wordt verdeeld in drie deelverzamelingen S\xe2\x82\x81, S\xe2\x82\x82, S\xe2\x82\x83 van ongeveer gelijke grootte, door middel van een eenvoudig te testen eigenschap._NEWLINE_Vervolgens wordt er een functie gedefinieerd die de groep afbeeldt op zichzelf waardoor de elementen op een andere manier worden gerangschikt. Verder wordt f(x) zo gekozen dat elk opeenvolgend element een functie is van alleen het voorgaande element. Eigenlijk worden twee reeksen elementen gemaakt waarbij de tweede reeks twee keer zo snel de groepselementen doorloopt als de eerste reeks. We zoeken nu totdat we twee dezelfde elementen hebben gevonden. Als we een element vinden dat voor de tweede keer voorkomt, is elk daaropvolgend element een herhaling van elementen eerder in de reeks._NEWLINE_De verjaardagenparadox zegt nu dat we zo\xe2\x80\x99n cyclus zullen vinden nadat we slechts O(\xe2\x88\x9ap) elementen van de reeks hebben berekend. (In het algemeen geldt dat als er volkomen willekeurig elementen worden geselecteerd uit een verzameling, met grootte n dan hoeft men maar O(\xe2\x88\x9ap) elementen van deze verzameling te selecteren om een kans van \xc2\xbd te hebben om hetzelfde element twee keer te trekken.)'