## You are here

HomePollard's $\rho$ algorithm

## Primary tabs

# Pollard’s $\rho$ algorithm

Pollard’s $\rho$ algorithm is an integer factorization algorithm devised by John Pollard in 1975 to take advantage of Floyd’s cycle-finding algorithm and pseudorandom number generation. Theoretically, trial division always returns a result (though of course in practice the computing engine’s resources could be exhausted or the user might not to be around to care for the result). Pollard’s $\rho$ algorithm, on the other hand, was designed from the outset to cope with the possibility of failure to return a result.

It can be left up to the implementer to choose a function $f(x)$ with a finite set of values that can be guaranteed to become cyclic quickly enough after few iterations. Crandall and Pomerance recommend $f(x)=x^{2}+a\mod n$, where $n$ is the number to be factored and $a$ is a pseudorandom number chosen based on $n$.

Choose a function $f(x)$ per the given requirements and call Pollard’s $\rho$ algorithm with $n$ a positive integer.

1. 2. Set $g=1$.

3. While $g==1$ and allowed number of iterations not exceeded, iterate $c=f(c)$ once and $d=f(d)$ twice and compute $g=GCD(c-d,n)$. The implementer may choose to take the absolute value of $c-d$, though some implementations of GCD don’t mind being given negative arguments.

4. If $g>1$, it is a factor of $n$. Otherwise, the algorithm has failed.

Take for example, $n=42$. Suppose our dice give us $a=12$ and $b=37$. I promise I didn’t choose these values consciously, but it happens that 37 does not change when input to $f(x)=x^{2}+12\mod 42$! 12 will change however, giving a sequence that continues 0, 20, 13. At 13, we find that $37-13=24$, and computing $GCD(24,42)$ gives up 6, which is not a prime, but is easily enough taken care of by trial division. The factorization is therefore $42=2\cdot 3\cdot 7$.

To date, the most well-known success of this algorithm was when Pollard and Richard Brent factored 115792089237316195423570985008687907853269984665640564039457584007913129639937 (the eighth Fermat number) in less than two hours, which was an impressive feat in 1975 for a UNIVAC 1100/42. Today, Mathematica running on a Dell with Windows XP factors that number in about 12 seconds (Mathematica’s `FactorInteger`

function has always used Pollard’s $\rho$ algorithm as one of the algorithms it uses).

## Mathematics Subject Classification

11A41*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections

## Comments

## Pollard's rho in Mathematica

Mathematica may be able to quickly factor F8, but it doesn't do it by Pollard's Rho algorithm. It uses ECM (ftp://ftp.comlab.ox.ac.uk/pub/Documents/techpapers/Richard.Brent/rpb161t...).

## Re: Pollard's rho in Mathematica

> Mathematica may be able to quickly factor F8, but it doesn't do it by Pollard's Rho algorithm. It uses ECM (ftp://ftp.comlab.ox.ac.uk/pub/Documents/techpapers/Richard.Brent/rpb161t...).

There is a way to make Mathematica show you the steps it takes to calculate something. I think it was in Theodore Glynn's book. Of course I could be wrong in assuming that it uses Pollard's rho. The program would have no nostalgia for how the number was first factored, it would simply choose the method most suitable for the number according to the way it was programmed.

I followed the link you provide but I'm having a hard time extracting the PostScript file from the archive. After that I'll have to figure out how to make my computer make me a PDF.

## Re: Pollard's rho in Mathematica

According to the Mathematica documentation (http://tinyurl.com/33pa2r), it currently uses:

"FactorInteger switches between trial division, Pollard p-1, Pollard rho, elliptic curve and quadratic sieve algorithms."

F8 factorization will take too long on both Pollard tests; ECM in the other hand finds it almost instantaneously, so I doubt QS has any chance of being used.

PS: the paper is just about the ECM, not about the claim on Mathematica's factoring algorithm; you can extract the .gz with 7-zip, and open the .ps with GSView/Ghostview.

## Re: Pollard's rho in Mathematica

> "FactorInteger switches between trial division, Pollard p-1, Pollard rho, elliptic curve and quadratic sieve algorithms."

That is exactly what the Mathematica 4.2 built-in help says. I thought about making my own Mathematica implementation of Pollard's rho, but I'm not that good a programmer. (I actually tried using Combinatorica::Partitions to find Goldbach representations of even numbers! It wasn't until the second draft of that that I switched to just subtracting odd numbers in order and then testing for primality).

I'll try 7-zip, but if there are no legal bugaboos, I'd much rather view the PostScript as a PDF in Adobe Reader.

## PS-PDF woe

>> I'll try 7-zip, but if there are no legal bugaboos, I'd much rather >> view the PostScript as a PDF in Adobe Reader.

Yeah, isn't is puzzeling that the founders of Adobe invented both PostScript and PDF but somehow their free PDF product doesn't read PostScript!

I've looked into the PDF, PS codec and the truth is they are both remarkably similar (though PDF does have compression and hypertext linking). After all, anything that can print to a laser printer must have in its code a PS codec, so why not have a full-fledged reader for PS!!

I'm with you PrimeFan, it is annoying. (...someday we can all be on Linux and this wont be a problem. :)

## Re: PS-PDF woe

But James, download GSView and Ghostscript from

http://pages.cs.wisc.edu/~ghost/

or

http://pages.cs.wisc.edu/~ghost/gsview/

Or I'm missing something?

perucho

## Re: PS-PDF woe

Yes, I know, I have had to use this when on Windows machines, but my lament is that PostScript is unusable to people who have a generic software setups. Ghost is a great product but I think Adobe reader should work with PostScript as well (as should Word for that matter.)

## Re: PS-PDF woe

I second the notion...it just isn't right...plus there are all these strange compatibility issues that I've encountered when including eps graphics in LaTeX documents generated using METAPOST, where FIRST I have to convert the file to ps, then use PS2PDF or whatever, and it's just annoying.