 |
Development of
Algorithmic Constructions |
 |
This is an idea for speeding up the Pollard-rho algorithm.
f is the number which should be factorized.
A base z is calculated for the power of p mod f, where p are all primes sorted from 3 to prime_max.
After a power of 10 a cycle detection is made.
A web implementation with C and Gmp can be found here
There is a good chance to factorize 30-40 digit numbers in less than 5 minutes on an Athlon 2x 5000+;
The runtime depends of the biggest factor of a-1 and of b-1, when f:=a*b;
- a:=nextprime (100000000);
b:=nextprime (200000000);
f:=a*b;
p:=3;
z:=9;
grenze:=1;
max_grenze:=100000000;
for i from 1 to max_grenze do
z:=powermod (z, p, f);
p:=nextprime (p+2);
if i=grenze then
x:=z;
y:=z;
if grenze<max_grenze then bis:=100;
else bis:=100000000;
end_if;
for j from 1 to bis do
x:=x^2 mod f;
y:=powermod (y, 4, f);
d:=gcd (x-y, f);
if d>1 then
print (f, "=", d,"*", f/d);
return (1);
end_if;
end_for;
grenze:=grenze*10;
end_if;
end_for;
20000004700000231, "=", 100000007, "*", 200000033