Pohlig-Hellman Algorithm for solving the DLP

Question

I read a website on The Pohlig-Hellman Algorithm for solving the DLP, in which it states that we can express $x$ as:

$x= a_0 + a_1p+ a_2p^2+...+ a_{e-1}p^{e-1}$, where $p^e$ is a prime factor of the order of the group.

We then can brute force all of $a_i$'s. But my question is, if we can figure out all $a_i$'s, why we can't state that $x$ just is $a_0 + a_1p+ a_2p^2+...+ a_{e-1}p^{e-1}$?

After all, we are assuming that $x=a_0 + a_1p+ a_2p^2+...+ a_{e-1}p^{e-1}$ anyway?
Why bother exhausting all prime factors?

Here is the source: https://risencrypto.github.io/PohligHellman/

Answer 1

From your question

$x= a_0 + a_1p+ a_2p^2+...+ a_{e-1}p^{e-1}$

This isn't exactly correct.

It should actually be

$x_i = a_0 + a_1{p_i}+ a_2{p_i}^2+...+ a_{e-1}{p_i}^{e-1}$

This is because you have to first convert the DLP in the group to a DLP in the subgroup.

Let $p-1 = p_1^{e_1}.p_2^{e_2}... p_n^{e_n}$

By Lagrange's Theorem, a cyclic group of order $p-1$ has a cyclic subgroup of corresponding to each of the factors & subfactors of the group.

If order of the group is $N = a*b*c$, then will be cyclic subgroup of order $a$, one of order $b$ & one of $c$.

If $g$ is the generator of the main group, then the generator for the subgroup of order $a$ is $g^{\frac {N} {a}}$.

So the subgroup of order $p_i^{e_i}$ has a generator $g^{\frac {p-1}{p_i^{e_i}}}$

Let the DLP of the main group be

$g^x = h \pmod p$

Let $r = \frac {p-1}{p_i^{e_i}}$

Let's raise both sides of the DLP by $r$

So $({g^x})^r = h^r \pmod p$

Can be rewritten as

$({g^r})^x = h^r \pmod p$ $g^r$ is the generator of the subgroup. Let's call it $g_i$

i.e. $g_i = g^r$.

So $g_i^x = h^r \pmod p$

Let $h_i = h^r$ & swap the left & right side

$h_i = g_i^x \pmod p$

This is now the DLP in the subgroup, since $g_i$ is the generator of the subgroup of order $p_i^{e_i}$

We can do a further simplification.

Since the order of the subgroup is $p_i^{e_i}$, when we solve for $x$ only in this subgroup, the maximum value of $x$ for the solution of the subgroup DLP can only be $p_i^{e_i}$

We can express this condition as a congruence.

$x = x_i \pmod {p_i^{e_i}}$

It's this $x_i$ which you expand as

$x_i = a_0 + a_1{p_i}+ a_2{p_i}^2+...+ a_{e-1}{p_i}^{e-1}$

And the subgroup DLP is

$h_i = g_i^{x_i} \pmod p$

When you solve the DLP in the subgroup, you get $x_i$ & not $x$.

So you have to solve the DLP in each of the $n$ subgroups to get

$x = x_1 \pmod {p_1^{e_1}}, x = x_2 \pmod {p_2^{e_2 }}, ..., x = x_n \pmod {p_n^{e_n}}$

Then you combine all of them with the Chinese Remainder Theorem to get $x$.

Hence to use your own words, you have to "exhaust all factors".