modlog {numbers}

Modular (or: Discrete) Logarithm

Description

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)

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.

Value

Returns an integer.

References

Forster, O. (1996). Algorithmische Zahlentheorie. Friedr. Vieweg u. Sohn Verlagsgesellschaft mbH, Wiesbaden.

See Also

primroot

Examples

modlog(11, 998, 1009)  # 505 , i.e., 11^505 = 998 mod 1009