<br><font size=2 face="sans-serif">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</font>
<br><font size=2 face="sans-serif">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</font>
<br><font size=2 face="sans-serif">in the NumberTheory addon package to
Mathematica for finding just the smallest prime factor, but I can't recall
offhand what it's called.</font>
<br>
<br><font size=2 face="sans-serif">Dave</font>
<br>
<br>
<br>
<br>
<br>
<table width=100%>
<tr valign=top>
<td width=40%><font size=1 face="sans-serif"><b>David Wasserman <dwasserm@earthlink.com></b>
</font>
<p><font size=1 face="sans-serif">05/07/2005 06:51 PM</font>
<td width=59%>
<table width=100%>
<tr valign=top>
<td>
<div align=right><font size=1 face="sans-serif">To</font></div>
<td><font size=1 face="sans-serif">seqfan@ext.jussieu.fr</font>
<tr valign=top>
<td>
<div align=right><font size=1 face="sans-serif">cc</font></div>
<td>
<tr valign=top>
<td>
<div align=right><font size=1 face="sans-serif">Subject</font></div>
<td><font size=1 face="sans-serif">Factoring large integers</font></table>
<br>
<table>
<tr valign=top>
<td>
<td></table>
<br></table>
<br>
<br>
<br><font size=2><tt>Does anyone have a routine to efficiently find one
prime factor of a number?<br>
<br>
Thanks,<br>
David<br>
</tt></font>
<br>