Pohlig-Hellman Algorithm for solving the DLP

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/

• I don't understand what you mean by " Why bother exhausting all prime factors?" Commented Nov 25, 2022 at 6:10
• The algorithm asks for all $p_i^{e_i}$. Commented Nov 25, 2022 at 6:16
• If you consider only $p_1$, then you will only find an $x$ which satisfies, $x = x_1 \bmod {p_1}^{n_1}$. You will similarly have to find $x = x_2 \bmod {p_2}^{n_2}$ & so on & then combine all of them using Chinese remainder theorem to find the $x$ which satisfies $\bmod p$ Commented Nov 25, 2022 at 6:27
• i am still confused tho, if that is the case, why our assumption states $x$ “is equal to” instead of “equivalent mod $p^e$“? Commented Nov 25, 2022 at 6:42
• @youngeAn: I dislike it, but fact is it's a common abuse of language to use "equal" for "equivalent modulo" (some obvious-to-the-writer quantity). Similarly people use all kinds of shorthands for $a\equiv b\pmod q$, e.g. $a=b\pmod q$, $a\equiv b\bmod q$, $a=b\bmod q$ (even though that conventionally implies $0\le a<q$, when $a\equiv b\pmod q$ does not), $a\equiv b$, and $a=b$.
– fgrieu
Commented Nov 25, 2022 at 6:46

$$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".