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;

             20000004700000231, "=", 100000007, "*", 200000033