Discrete Logarithm in $\mathbb{F}_p$ : Pohlig⁠-⁠Hellman

17 Dec 2021

§ Motivation

For some cases of the discrete logarithm problem, $g^x \equiv_p h$ , it is relatively easy to solve; for instance, when $\text{ord}_p(g)$ is "highly" composite, i.e. factorable by many small primes.

§ The Generalised Algorithm

Sps. we have an algorithm ( $\dagger$ ) to solve the discrete log over $\left(\mathbb{Z}_p\right)^\times$ when $g$ has prime power order, and $p$ prime. The generalised Pohlig-Hellman algorithm is dependent on the existence of ( $\dagger$ ).

About algorithm ( $\dagger$ ):

If using ( $\dagger$ ) on the discrete log described by $g^x \equiv_p h$ , if $\text{ord}_p(g) = q^{e}$ for some $q \in \mathbb{P_{\lt p}}$ , then suppose we can solve it in $\mathcal{O}(S_{q^e})$ time.
In the case where $e \ll q$ , then the value of $S_{q^e}$ can be expressed as $e\sqrt{p}$ , which means ( $\dagger$ ) can also be done in $\mathcal{O}(e\sqrt{p})$ time.
The algorithm exists and is described in Discrete Logarithm in $\mathbb{F}_p$ : $\text{ord}_p(g)$ is a Prime Power.

Generalised Pohlig-Hellman

Given $g^x \equiv_p h$ , and $N = \text{ord}_p(g) = \prod_{i = 1}^{t} q_i^{e_i}$ . Then, the discrete log can be solved using the Pohlig-Hellman algorithm:

For all $i \in [1 \dots t]$ , let
$g_i = g^{N/q_i^{e_i}}\ \text{and}\ h_i = h^{N/q_i^{e_i}}.$
Use alg. ( $\dagger$ ) to compute a sol'n for $y_i$ in $g_i^{y_i} \equiv_p h_i$ .
Using CRT, solve the following system of congruences:
$x \equiv \begin{cases} y_1 & \pmod{q_1^{e_1}}\\ y_2 & \pmod{q_1^{e_1}}\\ & \vdots\\ y_t & \pmod{q_t^{e_t}} \end{cases}$

The value of $x$ then satisfies $g^x \equiv_p h$ .

The discrete log can be solved by Pohlig-Hellman in $\mathcal{O}\left(\sum_{i=1}^{t} S_{q_i^{e_i}} + \log N\right)$ , assuming the complexity of ( $\dagger$ ) holds.

§ Computation

The Magma computational algebra system uses Pohlig-Hellman^[1] for the discrete log over $\mathbb{F}_p$ for $p \lt 2^{36}$ . Using Magma, we can compute

g^x \equiv_p h

with the following code:

// Replace g, h, p with values from the discrete log 
F<x> := FiniteField(p);

// The value satisfying the discrete log is stored in the variable x.
x := Log(F ! g, F ! h);

§ Sketch of Proofs

Complexity

In step (1) of Pohlig-Hellman, we solve $t$ discrete logs using ( $\dagger$ ); we assume that ( $\dagger$ ) is in $\mathcal{O}(S_{q^e})$ . Then, the upper bound of the first step is $\mathcal{O}\left(\sum_{i=1}^{t} S_{q_i^{e_i}}\right)$ .

In step (2) we solve a system of congruences using CRT. The CRT can be reduced into:

x \equiv \sum_{i=1}^{t}\left(N/q_i^{e_i}\right)y_ib_i,

where $b_i$ satisfies $b_i(N/q_i^{e_i}) \equiv 1 \pmod{q_i^{e_i}}$ . We compute $t$ $b_i$s with each taking $\mathcal{O}\left(\log\left(q_i^{e_i}\right)\right)$ , for all $b_i$s the time is $\mathcal{O}(\log(N))$ .

Then, the total runtime is indeed $\mathcal{O}\left(\sum_{i=1}^{t} S_{q_i^{e_i}} + \log N\right)$ .

Correctness

In step (2), by CRT $x$ satisfies all the congruences. Then, $x = y_i + q_i^{e_i}z_i\ (\ddagger)$ for some $z_i \in \mathbb{Z}$ .

\begin{align*} \left(g^x\right)^{N/q_i^{e_i}} &= \left(g^{y_i + q_i^{e_i}z_i}\right)^{N/q_i^{e_i}}\\ &= \left(g^{N/q_i^{e_i}}\right)^{y_i}g^{Nz_i}\\ &= \left(g^{N/q_i^{e_i}}\right)^{y_i}\\ &= g_i^{y_i}\\ &= h_i\\ &= h^{N/q_i^{e_i}} \end{align*}

Then, we notice that $(N/q_1^{e_1}, \dots, N/q_t^{e_t}) = 1$ , and that there exists $c_1, \dots, c_t$ satisfying

(c_1N/q_1^{e_1}, \dots, c_tN/q_t^{e_t}) = 1.

Finally,

g^x = g^{(\sum_{i=1}^{t}c_iN/q_i^{e_i})x}=h^{\sum_{i=1}^{t}c_iN/q_i^{e_i}}=h.

Magma Handbook, Discrete Logarithms. ↩︎

Discrete Logarithm in Fp\mathbb{F}_pFp​: Pohlig⁠-⁠Hellman

§ Motivation

§ The Generalised Algorithm

Generalised Pohlig-Hellman

§ Computation

§ Sketch of Proofs

Complexity

Correctness

Discrete Logarithm in $\mathbb{F}_p$ : Pohlig⁠-⁠Hellman