1
$\begingroup$

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/

$\endgroup$
6
  • $\begingroup$ I don't understand what you mean by " Why bother exhausting all prime factors?" $\endgroup$
    – user93353
    Nov 25, 2022 at 6:10
  • $\begingroup$ The algorithm asks for all $p_i^{e_i}$. $\endgroup$
    – youngeAn
    Nov 25, 2022 at 6:16
  • $\begingroup$ 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$ $\endgroup$
    – user93353
    Nov 25, 2022 at 6:27
  • $\begingroup$ i am still confused tho, if that is the case, why our assumption states $x$ “is equal to” instead of “equivalent mod $p^e$“? $\endgroup$
    – youngeAn
    Nov 25, 2022 at 6:42
  • 1
    $\begingroup$ @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$. $\endgroup$
    – fgrieu
    Nov 25, 2022 at 6:46

1 Answer 1

0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.