Special case of the Pohlig-Hellman algorithm

Suppose that $p, q_1, q_2$ are prime numbers such that $p - 1 = q_1 q_2$ with $q_1 \ne q_2$. Suppose that we can solve $g^x = h$ in $O(S_{q})$ if $\abs{g} = q$ for any $g, e \in \mathbb{F}_p$.

Note that an element in $\mathbb{F}_p$ has an order of $1, q_1, q_2, q_1q_2$. Therefore, we don’t have to worry about prime powers.

We claim that we can solve $g^x = h$ in $O(S_{q_1} + S_{q_2})$.

Let $g, h$ be given.

We assume $\abs{g} = q_1q_2$ as the other cases are trivial.

Now we solve the following two equations:

• $(g^{q_2})^{x_1} = h^{q_2}$.
• $(g^{q_1})^{x_2} = h^{q_1}$.

We can solve them in $O(S_{q_1} + S_{q_2})$ as $\abs{g^{q_2}} = q_1$ and $\abs{g^{q_1}} = q_2$. As $\gcd(q_1, q_2) = 1$, the CRT guarantees the existence of $x$ such that $x \equiv x_1 \pmod{q_1}$ and $x \equiv x_2 \pmod{q_2}$.

Let $k_1, k_2, c_1, c_2 \in \mathbb{Z}$ be chosen such that:

• $x = x_1 + k_1q_1$
• $x = x_2 + k_2q_2$
• $c_1q_1 + c_2q_2 = 1$

Then we have