Discrete Logarithm in $\mathbb{F}_p$: $\text{ord}_p(g)$ is a Prime Power
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$):
- We assume its time complexity is given by $\mathcal{O}(S_{q^e})$.
- The algorithm exists, and it is Shank’s Baby-Step Giant-Step algorithm.
($\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.
Pohlig-Hellman Algorithm on Wikipedia. ↩︎