Motivation§

The discrete logarithm problem (DLP), given by $g^x \equiv_p h$, can become easy to solve when $\text{ord}_p(g) = q^e$ for some $q \in \mathbb{P}, e \in \mathbb{Z}$.

The ($\dagger$) Algorithm§

I don’t know if this specific algorithm has a name, but I referred to it as algorithm ($\dagger$) in Discrete Logarithm in $\mathbb{F}_p$: Pohlig-Hellman. On Wikipedia it appears to just be referred to as a specific subroutine for Pohlig-Hellman when a group has prime power order1.

Sps. $p, q \in \mathbb{P}$, and there exists an algorithm ($\ddag\ddag$) that can solve the DLP over $\left(\mathbb{Z}_p\right)^\times$ when $\text{ord}_p(g) = q$. Again, we depend on algorithm ($\ddag\ddag$) for algorithm ($\dag$).

About algorithm ($\ddag\ddag$):

($\dagger$) Algorithm

Sps. we have a DLP $g^x \equiv_p h$ such that $\text{ord}_p(g) = q^e$.

  • First we solve for $x_0$ in $\left(g^{q^{e-1}}\right)^{x_0} \equiv_p h^{q^{e-1}}$
  • Then, for all $i \in [1\dots t]$ and $0 \leq x_i \lt q$ we solve:

$$ \left(g^{q^{e-1}}\right)^{x_i} \equiv_p \left(hg^{\sum_{n=0}^{i-1}-x_{n}q^n}\right)^{q^{e-1-i}} $$

These congruences can be solved using algorithm ($\ddag\ddag$).

Finally, the sol’n is given by

$$ x = \sum_{n=0}^{e-1}\left(x_nq^n\right). $$

The sol’n of the DLP can be found using ($\dag$) in $\mathcal{O}(eS_{q^e})$ time, provided our assumption of the time complexity for algorithm ($\ddag\ddag$) holds.

  1. Pohlig-Hellman Algorithm on Wikipedia. ↩︎