Discrete logarithm

In abstract algebra and its applications, the discrete logarithms are defined in group theory in analogy to ordinary logarithms.

Related Topics:
Abstract algebra - Group theory - Logarithm

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Discrete logarithms are perhaps simplest to understand in the group (Zp)×. This is the set {1, …, p − 1} under multiplication modulo the prime p. If we want to find the kth power of one of the numbers in this group, called discrete exponentiation, we do so by finding its kth power as an integer and then finding the remainder after division by p. For example, 3 to the 5th power is 243, and when we divide 243 by 7 the remainder is 5; thus, 35 in the group (Z7)× is 5. Once we have discrete exponentiation, discrete logarithm is just the inverse operation: given that 3k ≡ 5 (mod 7), what is the smallest k that makes this true?

Related Topics:
Modulo - Prime

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

More generally, let G be a finite cyclic group with n elements. We assume that the group is written multiplicatively. Let b be a generator of G; then every element x of G can be written in the form x = bk for some integer k. Furthermore, any two such integers representing x will be congruent modulo n. We can thus define a function

Related Topics:
Cyclic group - Generator - Modulo

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

:log_b: G ightarrow mathbf{Z}_n

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

(where Zn denotes the ring of integers modulo n) by assigning to x the congruence class of k modulo n. This function is a group isomorphism, called the discrete logarithm to base b.

Related Topics:
Ring - Group isomorphism

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

The familiar base change formula for ordinary logarithms remains valid: if c is another generator of G, then we have

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

:log_c (x) = log_c(b) cdot log_b(x).

~ ~ ~ ~ ~ ~ ~ ~ ~ ~