|
|
D.12.3.15 rho
Procedure from library crypto.lib (see crypto_lib).
- 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)
Example:
| | LIB "crypto.lib";
bigint b=2;
bigint y=10;
bigint p=101;
rho(b,y,p);
==> 25
|
|
