Realizes the modular (or discrete) logarithm modulo a prime number
\(p\), that is determines the unique exponent \(n\) such that
\(g^n = x \, \mathrm{mod} \, p\), g a primitive root.
Usage
modlog(g, x, p)
Value
Returns an integer.
Arguments
g
a primitive root mod p.
x
an integer.
p
prime number.
Details
The method is in principle a complete search, cut short by "Shank's
trick", the giantstep-babystep approach, see Forster
(1996, pp. 65f). g has to be a primitive root modulo p,
otherwise exponentiation is not bijective.
References
Forster, O. (1996). Algorithmische Zahlentheorie. Friedr. Vieweg u.
Sohn Verlagsgesellschaft mbH, Wiesbaden.