Singular

D.12.2.17 rho

Usage:

rho(b,y,p);

Return:

the discrete logarithm x=log_b(y): b^x=y mod p

Note:

Pollard's rho:
choose random f_0 in 0,...,p-2 ,e_0=0, define x_0=b^f_0, define x_i=y^e_i*b^f_i as below. For i large enough there is i with x_(i/2)=x_i. Let s:=e_(i/2)-e_i mod p-1 and t:=f_i-f_(i/2) mod p-1, d=gcd(s,p-1)=u*s+v*(p-1) then x=tu/d +j*(p-1)/d for some j (to be found by trying)

LIB "crypto.lib";
bigint b=2;
bigint y=10;
bigint p=101;
rho(b,y,p);
==> 25