Devil's Night

The discrete logarithm  was introduced by Diffie-Hellman Key Exchange. Let’s take a close look at this problem.

Example

Let’s pick up a prime number 7, then there will be a cyclic group C_n, when n = 2, C₂ = {1, 2, 3, 4, 5, 6 ,}. Every element in this group is co-prime with 7, and there would be a generator g. In this example g = 7. We can verify that by calculation

• 3¹ mod 7 = 3
• 3² mod 7 = 2
• 3³ mod 7 = 6
• 3⁴ mod 7 = 4
• 3⁵ mod 7 = 5
• 3⁶ mod 7 = 1

Discrete logarithm is just the inverse operation.
For instance, an equation like this: 3^k ≡ 6 (mod 7), as shown above k = 3 is the root, but it’s not the only solution, we can find there is also 3⁹ ≡ 6(mod 7). What more this expression 3³⁺⁹ⁿ ≡ 6 (mod 7) satisfies k forever as long as n is a natural number. Moreover, since 3 is the smallest positive integer k satisfying 3^k ≡ 1 (mod 7), i.e. 3 is the order of 3 in (Z₇)*, these are the only solutions. Equivalently, the solution can be expressed as k ≡ 3 (mod 7).

Definition

In general, 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 g of G can be written in the form g = b^k for some integer k. Furthermore, any two such integers representing g will be congruent modulo n. We can thus define a function

• log_b: G→Z

Computing discrete logarithms is apparently difficult. Not only is no efficient algorithm known for the worst case, but the average-case complexity can be shown to be at least as hard as the worst case using random self-reducibility.
So discrete logarithm is the foundation of Diffie-Hellman Key Exchange