] >
Blijkt uit een priemtest dat een getal samengesteld is, dan wil dat niet zeggen dat je in staat bent het getal te factoriseren. Dat is de basis van een aantal cryptografische toepassingen. Er zijn betere methodes dan alleen domweg proberen delers te vinden. Een van die methodes is in 1975 geïntroduceerd door J. Pollard en staat bekend als Pollard-rho. Later zijn er nog andere en snellere methodes bedacht. We beschrijven hier alleen Pollard-rho.
Laat gegeven zijn een transformatie van en een natuurlijk getal . Daarbij willen we dat zo is dat hij voor iedere een transformatie van induceert, dus dat voor alle uit volgt dat . Iedere afbeelding van de vorm , waarbij , voldoet hieraan. Bekijk de rij getallen
Voor iedere geldt dat in de rij
in een herhaling optreedt, zeg met , want de verzameling is eindig. Dan voor alle . Teken een plaatje van deze rij en hoe op de termen van de rij werkt en je weet waarom rho in de naam van het algoritme voorkomt. Is een getal samengesteld dan hoef je voor het berekenen van de getallen alleen te weten wat de getallen modulo zijn. Dus kun je ervoor zorgen dat de getallen in de rij natuurlijke getallen zijn. Zodra je en hebt gevonden met , heb je een niet-triviale deler van , namelijk .
Laat een priemdeler van zijn. Na hoeveel termen in de rij kun je verwachten dat ? Hoeveel termen verwacht je te moeten berekenen om twee termen te vinden die congruent zijn modulo ? Dit is een variant op het verjaardagsprobleem, zie ook 9.4. Het te verwachte aantal is in de orde van , of nauwkeuriger .
Bij een gegeven kun je een willekeurige als startwaarde kiezen. Ook de (als de transformatie is) kan willekeurig gekozen worden. Omdat het verloop van het algoritme, en daarmee ook het succes ervan, van deze willekeurige keuzes afhangt spreekt man wel van een Monte-Carlomethode.
Er zijn allerlei trucs om het proces te bekorten door er voor te zorgen dat de niet vaak hoeft te worden uitgerekend en, wat ook belangrijk is, de getallen niet onthouden behoeven te worden. Een fraaie manier, de Floyd cycle finding method, is om alleen de verschillen te bekijken: het verschil van en zal voor zekere een veelvoud van de lengte van de periode zijn terwijl tegelijkertijd voorbij het begin van de periode is.
Pollard-rho met gebruikmaking van de Floyd cycle finding method is in Python eenvoudig te beschrijven. De startwaarde en de in de functie worden willekeurig gekozen. Eenzelfde input kan dus verschillende uitkomsten geven.
We hebben nu:
In principe is het eerste algoritme voldoende voor het factoriseren van een getal. Het probleem is dat het op die manier veel en veel te lang kan duren. Voor ‘grote’ getallen kunnen we de andere algoritmen gebruiken om een priemfactorontbinding te vinden. Bijvoorbeeld:
Al met al kan er een hele boekhouding nodig zijn om het allemaal bij te houden. Dat is natuurlijk te automatiseren, maar dat doen we hier niet. We doen het met de hand en gebruiken daarbij de computer, interactief dus.
We nemen een .
Er zijn geen priemdelers kleiner dan .
Het is geen priemgetal.
Er is een deler gevonden. Dit is een priemgetal, want anders is er een priemdeler en die zou al eerder gevonden zijn. De andere factor, het getal , is waarschijnlijk een priemgetal. We gaan bewijzen dat een priemgetal is met de -test.
Het getal is waarschijnlijk priem en we gaan weer de -test toepassen.
De gevonden delers van zijn klein genoeg om te concluderen dat zij priem zijn. Uit de -test volgt dat priem is. Nogmaals de -test geeft dat priem is. We hebben dus de priemfactorontbinding van :
In dit voorbeeld kwam het goed uit dat met Pollard-rho de factor werd gevonden. Dat deze factor relatief klein is maakt dat hij snel wordt gevonden.