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);
for i from 1 to max_grenze do
z:=powermod (z, p, f);
if i=grenze then
if grenze<max_grenze then bis:=100;
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);
20000004700000231, "=", 100000007, "*", 200000033