Discrete Logarithm -- from MathWorld

If a is an arbitrary integer relatively prime to n and g is a primitive root of n, then there exists among the numbers 0, 1, 2, ..., exactly one number such that

The number is then called the discrete logarithm (or generalized multiplicative order; Schneier 1996, p. 501) of a with respect to the base g modulo n. Note that Nagell (1951, p. 112) instead uses the term "index" and writes

For example, the number 7 is the least positive primitive root of n = 41, and since , the number 15 has multiplicative order 3 with respect to base 7 (modulo 41) (Nagell 1951, p. 112). The generalized multiplicative order is implemented in Mathematica as MultiplicativeOrder[a, n, {g1}], or more generally as MultiplicativeOrder[a, n, {g1, g2, ...}].

Multiplicative Order

Nagell, T. "Exponent of an Integer Modulo n" and "The Index Calculus." �31 and 33 in Introduction to Number Theory. New York: Wiley, pp. 102-106 and 111-115, 1951.

Schneier, B Applied Cryptography: Protocols, Algorithms, and Source Code in C, 2nd ed. New York: Wiley, 1996.

Eric W. Weisstein. "Discrete Logarithm." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/DiscreteLogarithm.html

� 1999-2005 Wolfram Research, Inc.