Discrete Logarithm in Fp\mathbb{F}_p: ordp(g)\text{ord}_p(g) is a Prime Power

17 Dec 2021

Notes Cryptography

Discrete Logarithm in Fp\mathbb{F}_p: ordp(g)\text{ord}_p(g) is a Prime Power

§ Motivation

The discrete logarithm problem (DLP), given by gx≡phg^x \equiv_p h, can become easy to solve when ordp(g)=qe\text{ord}_p(g) = q^e for some q∈P,e∈Zq \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 Fp\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 order[1].

Sps. p,q∈Pp, q \in \mathbb{P}, and there exists an algorithm (‡‡\ddag\ddag) that can solve the DLP over (Zp)×\left(\mathbb{Z}_p\right)^\times when ordp(g)=q\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 gx≡phg^x \equiv_p h such that ordp(g)=qe\text{ord}_p(g) = q^e.

  • First we solve for x0x_0 in (gqe−1)x0≡phqe−1\left(g^{q^{e-1}}\right)^{x_0} \equiv_p h^{q^{e-1}}
  • Then, for all i∈[1…t]i \in [1\dots t] and 0≤xi<q0 \leq x_i \lt q we solve:

(gqe−1)xi≡p(hg∑n=0i−1−xnqn)qe−1−i\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=∑n=0e−1(xnqn).x = \sum_{n=0}^{e-1}\left(x_nq^n\right).

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

  1. Pohlig-Hellman Algorithm on Wikipedia. ↩︎