# Pollard's $\rho$ algorithm

## Primary tabs

Synonym:
Pollard $\rho$ algorithm, Pollard's rho algorithm, Pollard rho algorithm
Major Section:
Reference
Type of Math Object:
Algorithm

## Mathematics Subject Classification

### 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. :)