Motivation§

For some cases of the discrete logarithm problem (DLP), $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 DLP 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 DLP 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 DLP can be solved using the Pohlig-Hellman algorithm:

  1. 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$.

  2. 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 DLP 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-Hellman1 for the DLP 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 DLP 
F<x> := FiniteField(p);

// The value satisfying the DLP 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$ DLPs 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. $$

  1. Magma Handbook, Discrete Logarithms. ↩︎