|
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