Fork me on GitHub
Math for the people, by the people.

User login

Pollard's $\rho$ algorithm

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

Mathematics Subject Classification

11A41 no label found

Comments

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

> 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.

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.

> "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.

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

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

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

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.

Subscribe to Comments for "Pollard's $\rho$ algorithm"