Home Online Manual
Top
Back: babyGiant
Forward: MillerRabin
FastBack:
FastForward:
Up: crypto_lib
Top: Singular Manual
Contents: Table of Contents
Index: Index
About: About this document

D.12.2.17 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