|
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 factorization of the [[Fermat number]] {{math|''F''<sub>8</sub>}} = 1238926361552897 × 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|doi-access=free }}</ref> The ''ρ'' algorithm was a good choice for {{math|''F''<sub>8</sub>}} because the prime factor {{mvar|p}} = 1238926361552897 is much smaller than the other factor. The factorization took 2 hours on a [[UNIVAC]] [[UNIVAC 1110|1100/42]].<ref name="FotEFN" />
== TheExample: examplefactoring {{mvar|n}} = 10403 = 101 · 103 ==
In this example, only a single sequence is computed, and the {{math|''gcd''}} is computed inside the loop that detects the cycle.
In following table shows numbers produced by the algorithm, starting with <math>x=2</math> and using the polynomial <math>g(x) = (x^2 + 1) \bmod 10403</math>.
=== C code sample ===
The third and fourth columns of the table contain additional information not known by the algorithm.
The following code sample finds the factor 101 of 10403 with a starting value of {{mvar|x}} = 2.
They are included to show how the algorithm works.
<syntaxhighlight lang="c">
#include <stdio.h>
#include <stdlib.h>
int gcd(int a, int b)
{
int remainder;
while (b != 0) {
remainder = a % b;
a = b;
b = remainder;
}
return a;
}
int main (int argc, char *argv[])
{
int number = 10403, loop = 1, count;
int x_fixed = 2, x = 2, size = 2, factor;
do {
printf("---- loop %4i ----\n", loop);
count = size;
do {
x = (x * x + 1) % number;
factor = gcd(abs(x - x_fixed), number);
printf("count = %4i x = %6i factor = %i\n", size - count + 1, x, factor);
} while (--count && (factor == 1));
size *= 2;
x_fixed = x;
loop = loop + 1;
} while (factor == 1);
printf("factor is %i\n", factor);
return factor == number ? EXIT_FAILURE : EXIT_SUCCESS;
}
</syntaxhighlight>
The above code will show the algorithm progress as well as intermediate values.
The final output line will be "factor is 101". The code will only work for small test values as overflow will occur in integer data types during the square of x.
=== Python code sample ===
<syntaxhighlight lang="python">
from itertools import count
from math import gcd
import sys
number, x = 10403, 2
for cycle in count(1):
y = x
for i in range(2 ** cycle):
x = (x * x + 1) % number
factor = gcd(x - y, number)
if factor > 1:
print("factor is", factor)
sys.exit()
</syntaxhighlight>
=== The results ===
In the following table the third and fourth columns contain secret information not known to the person trying to factor {{mvar|pq}} = 10403. They are included to show how the algorithm works. Starting with {{mvar|x}} = 2, the algorithm produces the following numbers:
{| class="wikitable" style="text-align:right;"
! {{tmath|x}} !! {{tmath|x_\text{fixed}y }} !! {{tmath|x \bmod 101}} !! {{tmath|x_\text{fixed}y \bmod 101}} !! step
|-
| 2 || 2 || 2 || 2 || 0
|}
The first repetition modulo 101 is 97 which occurs in step 17. The repetition is not detected until step 23, when <math>x \equiv x_\text{fixed}y \pmod{101}</math>. This causes <math>\gcd (x - x_\text{fixed}y, n) = \gcd (2799 - 9970, n)</math> to be <math>p = 101</math>, and a factor is found.
== Complexity ==
| 