Pollard's rho algorithm: Difference between revisions

Revision as of 07:00, 4 February 2024

Revision as of 07:11, 4 February 2024

Line 60:

== Application ==

The algorithm is very fast for numbers with small factors, but slower in cases where all factors are large. The ''ρ'' algorithm's most remarkable success was the 1980 factorization of the [[Fermat number]] {{math|''F''₈}} = 1238926361552897&nbsp;×&nbsp;93461639715357977769163558199606896584051237541638188580280321.<ref name="FotEFN">{{cite journal |last1=Brent |first1=R.P. |last2=Pollard |first2=J. M. |year=1981 |title=Factorization of the Eighth Fermat Number |journal=Mathematics of Computation |volume=36 |issue=154 |pages=627–630 |doi=10.2307/2007666|jstor=2007666 |doi-access=free }}</ref> The ''ρ'' algorithm was a good choice for {{math|''F''₈}} because the prime factor {{mvar|p}} = 1238926361552897 is much smaller than the other factor. The factorization took 2 hours on a [[UNIVAC]] [[UNIVAC 11101100|1100/42]].<ref name="FotEFN" />

== Example: factoring {{mvar|n}} = 10403 = 101 · 103 ==