Score:1

Pohlig-Hellman Algorithm for solving the DLP

ai flag

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/

et flag
I don't understand what you mean by " Why bother exhausting all prime factors?"
youngeAn avatar
ai flag
The algorithm asks for all $p_i^{e_i}$.
et flag
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$
youngeAn avatar
ai flag
i am still confused tho, if that is the case, why our assumption states $x$ “is equal to” instead of “equivalent mod $p^e$“?
fgrieu avatar
ng flag
@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$.
SAI Peregrinus avatar
si flag
And some programming languages, like C, mix up mod and remainder.
Score:0
et flag

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

I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.