TOPICS
Search

Discrete Logarithm


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, ..., phi(n)-1, where phi(n) is the totient function, exactly one number mu such that

 a=g^mu (mod n).

The number mu is then called the discrete logarithm of a with respect to the base g modulo n and is denoted

 mu=ind_ga (mod n).

The term "discrete logarithm" is most commonly used in cryptography, although the term "generalized multiplicative order" is sometimes used as well (Schneier 1996, p. 501). In number theory, the term "index" is generally used instead (Gauss 1801; Nagell 1951, p. 112).

For example, the number 7 is a positive primitive root of n=41 (in fact, the set of primitive roots of 41 is given by 6, 7, 11, 12, 13, 15, 17, 19, 22, 24, 26, 28, 29, 30, 34, 35), and since 15=7^3 (mod 41), 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 the Wolfram Language as MultiplicativeOrder[g, n, {a1}], or more generally as MultiplicativeOrder[g, n, {a1, a2, ...}].

Discrete logarithms were mentioned by Charlie the math genius in the Season 2 episode "In Plain Sight" of the television crime drama NUMB3RS.


See also

Multiplicative Order, Primitive Root

Explore with Wolfram|Alpha

References

Gauss, C. F. §57 in Disquisitiones Arithmeticae. Leipzig, Germany, 1801. Reprinted New Haven, CT: Yale University Press, 1965.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.

Referenced on Wolfram|Alpha

Discrete Logarithm

Cite this as:

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

Subject classifications