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

Arguments

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