Factoring large integers

[David C Terr]

Trial division works best for small prime factors (i.e. up to 10^10 or so, 
depending on the computer system used). For intermediate prime factors 
(roughly 10^10 to 10^20), Pollard rho and Pollard p-1 can be used. For 
large prime factors (greater than 10^20), the elliptic curve method should 
first be tried, followed by the quadratic sieve or the number field sieve, 
depending
on the size of the number being factored. FactorInteger in Mathematica 
versions 4.0 and up uses all these methods except for the number field 
sieve. I believe there's also a routine
in the NumberTheory addon package to Mathematica for finding just the 
smallest prime factor, but I can't recall offhand what it's called.

Dave





David Wasserman <dwasserm at earthlink.com> 
05/07/2005 06:51 PM

To
seqfan at ext.jussieu.fr
cc

Subject
Factoring large integers






Does anyone have a routine to efficiently find one prime factor of a 
number?

Thanks,
David

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.seqfan.eu/pipermail/seqfan/attachments/20050509/c1cdbd95/attachment-0001.htm>