O. Forster: Algorithmic Number Theory

5. The Discrete Logarithm

5.1. Definition. Let p be a prime. As we have proved in chapter 4, the multiplicative group (ℤ/p)^{∗} is cyclic. A generator g of this group is called a primitive root modulo p. The map

exp_{g} : (ℤ/(p − 1), +) ⟶ (ℤ/p)^{∗}, k ↦ g^{k},

is an isomorphism of the additive group ℤ/(p−1) onto the multiplicative group (ℤ/p)^{∗}. Its inverse is called the discrete logarithm with respect to base g,

log_{g} : (ℤ/p)^{∗} ⟶ ℤ/(p − 1).

Classically, log_{g}(x) is also called the index of x with respect to the primitive root g.

In this chapter we will discuss the discrete logarithm in a slightly more general setting: Let G be a (multiplicative) cyclic group of order m and g a generator of G. Again we have a group isomorphism

exp_{g} : (ℤ/m, +) ⟶ G, k ↦ g^{k},

and we are interested in its inverse

log_{g} : G ⟶ ℤ/m.

By definition

log_{g}(x) = k ⟺ x = g^{k}.

Whereas the exponential map can be efficiently calculated using the fast exponentiation algorithm, it is in general much more complicated to calculate the discrete logarithm. This asymmetry is used by some cryptographic systems.

5.2. Shanks’ Giant-Step-Baby-Step Method. The naive method to calculate the discrete logarithm of x is to calculate g^{k} for k = 0, 1, 2, 3, … until one finds a match g^{k} = x. The complexity of this method is O(m). Shanks has devised a quite general method which reduces this complexity to about O(\sqrt{m}), which we will now describe. Let G be a cyclic group of order m with generator g. We want to calculate the discrete logarithm of a given element x ∈ G, i.e. find an integer k with 0 ≤ k < m and

g^{k} = x.

Set r := ⌈\sqrt{m} ⌉, i.e. r is the least integer ≥ \sqrt{m}. The unknown logarithm k can be written as

k = αr + β with 0 ≤ α, β < r.

Chap. 5 last revised: 2002-05-13 5.1

5. The discrete logarithm

The equation g^{k} = x is equivalent to

g^{αr} = xg^{−β}.

To solve this equation, we first calculate the ‘giant steps’

g^{νr} = (g^{r})^{ν} for ν = 0, 1, 2, …, r − 1

and store them. Next we calculate the ‘baby steps’

xg^{−μ} for μ = 0, 1, 2, …

and compare them with the giant steps until a match g^{αr} = xg^{−β} is found. Then k = αr + β is the discrete logarithm of x.

What is the complexity of this method? The calculation of the giant steps and baby steps has a complexity of O(\sqrt{m}). The critical point is comparing the baby steps with the giant steps. Since we have up to \sqrt{m} baby steps, it is not acceptable to do every time a linear search in the table of giant steps. A better way is to use binary search which needs O(log m) steps for one search. This supposes the table of giant steps to be sorted, which can be done (e.g. by a suitable quicksort algorithm) in O(\sqrt{m} log m) steps. This leads to an overall complexity of O(\sqrt{m} log m). Still better is to use appropriate hashing techniques. Then a lookup in the table of giant steps can be done in almost constant time, so we get a complexity of O(\sqrt{m}). A disadvantage of this method is the high space requirement of order O(\sqrt{m}) for the table of giant steps. There is a probabilistic variant of the algorithm (which we will discuss in a later chapter) which needs only a small constant amount of space.

If the order m of the group G is not a prime number, one can reduce the discrete logarithm problem for G to smaller groups. For this purpose we need some preparations.

5.3. Theorem. Let G be a (multiplicative) cyclic group of order m with generator g. Then for every positive divisor k | m there exists exactly one subgroup G(k) ⊂ G of order k. This group can be described in the following ways:

i) G(k) = {x ∈ G : x^{k} = e}.

ii) G(k) = Im(ϕ), where ϕ is the map

ϕ : G ⟶ G, x ↦ x^{m/k}.

iii) G(k) is the cyclic subgroup of G generated by g^{m/k}.

Proof. Define G_{1} := {x ∈ G : x^{k} = e}. Certainly any subgroup of G with k elements is contained in G. If we can show that G_{1} has k elements, we have proved unicity. Every element x ∈ G has the form x = g^{ν} with 0 ≤ ν < m. We have

x = g^{ν} ∈ G_{1} ⟺ g^{νk} = e ⟺ m | νk ⟺ (m/k) | ν.

5.2 This shows that G_{1} = {g^{(m/k)μ} : 0 ≤ μ < k} which has indeed k elements and is the group described in iii). Because G is generated by g, the group Im(ϕ) in ii) is generated by g^{m/k}, which implies that the groups described in ii) and iii) coincide. This completes the proof of the theorem.

5.4. Theorem. Let G be a cyclic group of order m. Suppose that

m = m_{1}m_{2} · . . . · m_{r}

with pairwise coprime m_{i} ≥ 2 and let G_{i} be the uniquely determined subgroup of G of order m_{i}. Since gcd(m/m_{1}, m/m_{2}, …, m/m_{r}) = 1, there exist integers λ_{i} with

λ_{1} · \frac{m}{m_{1}} + … + λ_{r} · \frac{m}{m_{r}} = 1.

Consider the maps

G ⟶^{ϕ} G_{1} × G_{2} × … × G_{r} ⟶^{ψ} G,

where ϕ and ψ are defined by

ϕ(x) := (x^{m/m_{1}}, …, x^{m/m_{r}}), ψ(x_{1}, …, x_{r}) := x_{1}^{λ_{1}} · . . . · x_{r}^{λ_{r}}.

Then ϕ and ψ are isomorphisms with ψ ∘ ϕ = id_{G}.

Proof. The equation ψ ∘ ϕ = id_{G} follows directly from the definition of the integers λ_{i}. Since the groups G and G_{1} × G_{2} × … × G_{r} have the same number of elements, it follows that ϕ and ψ are isomorphisms.

5.5. Pohlig-Hellman reduction. We now apply theorem 5.4 to the discrete logarithm problem. We keep the notations of 5.4. Let g ∈ G be a generator and x ∈ G an element whose discrete logarithm is to be calculated. We apply the map ϕ to g and x.

G ⟶^{ϕ} G_{1} × … × G_{r}
g ↦ (g_{1} , …, g_{r}) , g_{i} = g^{m/m_{i}}
x ↦ (x_{1} , …, x_{r}) , x_{i} = x^{m/m_{i}}

The element g_{i} is a generator of the group G_{i} of order m_{i}, therefore we can solve the discrete logarithm problem in G_{i} with respect to base g_{i} and get integers k_{i} with

x_{i} = g_{i}^{k_{i}} for i = 1, …, r.

By theorem 5.4 we have

x = x_{1}^{λ_{1}} · . . . · x_{r}^{λ_{r}} = g_{1}^{k_{1}λ_{1}} · . . . · g_{r}^{k_{r}λ_{r}} = g^{k_{1}λ_{1}m/m_{1}+...+k_{r}λ_{r}m/m_{r}},

therefore

k := ∑_{i=1}^{r} k_{i} λ_{i} \frac{m}{m_{i}} mod m ∈ ℤ/m

5.3 is the discrete logarithm of x ∈ G with respect to base g.

Since every positive integer m can be decomposed into a product of prime powers, m = ∏_{i=1}^{r} p_{i}^{k_{i}}, we see that the discrete logarithm problem in an arbitrary finite cyclic group can be reduced to the discrete logarithm problem in cyclic groups of prime power order. We will show next how to further reduce the problem to groups of prime order.

5.6. Cyclic groups of prime power order. Let G be a cyclic group of order p^{n}, where p is a prime and n an integer ≥ 2. Let g be a generator of G. We want to solve the discrete logarithm problem in G, i.e. given an element z ∈ G, find an integer t such that g^{t} = z. For k = 1, 2, …, n we define the subgroups

G(p^{k}) := {x ∈ G : x^{p^{k}} = e}.

By theorem 5.3, G(p^{k}) is a cyclic group of order p^{k} and the map

G → G(p^{k}), x ↦ x^{p^{n−k}},

is surjective. We have the filtration

G = G(p^{n}) ⊃ G(p^{n−1}) ⊃ … ⊃ G(p^{2}) ⊃ G(p) ⊃ {e}.

We suppose that we have an algrithm to solve the discrete logarithm problem in G(p) (for example Shanks’ giant-step-baby-step method). Given z ∈ G, we will show by induction on k how to find integers t_{k} such that

(g^{t_{k}})^{p^{n−k}} = z^{p^{n−k}}.

The case k = n solves the discrete logarithm problem in G. Since g^{p^{n−1}} is a generator of G(p), the case k = 1 is the discrete logarithm problem in G(p). Induction step k → k + 1. By induction hypothesis we have

(g^{t_{k}})^{p^{n−k}} = z^{p^{n−k}} ⟹ (zg^{−t_{k}})^{p^{n−k}} = e ⟹ ((zg^{−t_{k}})^{p^{n−k−1}})^{p} = e.

Therefore

y_{k} := (zg^{−t_{k}})^{p^{n−k−1}} ∈ G(p),

and solving the discrete logarithm problem in G(p) yields an integer τ_{k} with

(g^{p^{n−1}})^{τ_{k}} = y_{k} = (zg^{−t_{k}})^{p^{n−k−1}}.

This implies

(zg^{−t_{k}−τ_{k}p^{k}})^{p^{n−k−1}} = e ⟹ (g^{t_{k}+τ_{k}p^{k}})^{p^{n−k−1}} = z^{p^{n−k−1}}.

With t_{k+1} := t_{k} + τ_{k}p^{k}, this is the induction assertion for k + 1, q.e.d.

5.7. Conclusion. Let G be a cyclic group of order m and let

m = ∏_{i=1}^{r} p_{i}^{k_{i}}

be the prime factorization of m. Then, using the Pohlig-Hellman reduction and Shanks’ giant-step-baby-step method, the discrete logarithm in G can be calculated in about O(\sqrt{p}) steps, where p = max\{p_{i} : 1 ≤ i ≤ r\}.

5.4