Development of
Algorithmic Constructions

This is an idea for speeding up the Pollard-rho algorithm for Mersenne numbers.

Instead of using a quadratic polynom, you can use a polynom with degree of p, because the mersenne numbers Mp have a cyclic group of p.

p:=11;
mp:=2^p-1;
x:=3;
y:=x;
anz:=0;
while TRUE do
    x:=powermod (x, p, mp)-1;
    y:=powermod (y, p, mp)-1;
    y:=powermod (y, p, mp)-1;
    anz:=anz+1;
    d:=x-y;
    res:=gcd (d, mp);
    if res>1 then
       print ("Fakor = ", res, "Anzahl der Iterationen =", anz);
       break;
    end_if;
end_while;

               "Fakor = ", 23, "Anzahl der Iterationen =", 3

Development ofAlgorithmic Constructions

Development of
Algorithmic Constructions