1
$\begingroup$

I'm trying to use the Pohlig-Hellman algorithm to solve for $x$ where $15^x=131 \bmod 337$. This is what I have so far:

Prime factors of $p-1$: $336=2^4\cdot3\cdot7$

$q=2$: $x=2^0\cdot x_0+2^1\cdot x_1+2^2\cdot x_2+2^3\cdot x_3$

$x_0$: $131^{168}=15^{168*x_0}$, $-1(\bmod 337) = (-1)^{x_0}(\bmod 337)$, $x_0=1$

$x_1: 131*15^{-1}=131*45=166 \bmod337$, $166^{184}=15^{168\cdot x_1}$, $148 \bmod 337= -1^{x_1}\bmod 337$

However, from there, $x_1$ has no answer. So I know I've done something wrong, I just don't see what. I've double- and triple-checked every computation, so I assume I misunderstand something about the algorithm.

$\endgroup$
1
$\begingroup$

When solving for $x$ in the equation $g^x \equiv h \text{ mod } p$ the idea behind Pohlig Hellman is to solve discrete logs on group elements with smaller orders and then recombine those results to obtain $x$. For each prime factor $q^e$ of $p-1$ you do the following:

  1. Find an element with order $q^e$. You can do this via $g' = g^{\frac{n}{q^e}} \text{ mod } p$.
  2. Compute $h' = h^{\frac{n}{q^e}} \text{ mod } p$.
  3. Now, via e.g. brute force find $x'$ such that ${g'}^{x'} \equiv h' \text{ mod } p$. Note that since the group order of the group is $q^e$ this should be fairly quick as long as $p-1$ is smooth.

Using your example we obtain:

  • For $q^e = 2^4$: $$g_1 = 278, h_1 = 148, x_1 = 12$$
  • For $q^e = 3^1$: $$g_2 = 208, h_2 = 128, x_2 = 2$$
  • For $q^e = 7^1$: $$g_3 = 79, h_3 = 53, x_3 = 5$$

We now need to use the Chinese remainder theorem to recombine all our $x_i$ to solve for $x$ using the follow congruences:

$$x \equiv 12 \text{ mod } 2^4$$ $$x \equiv 2 \text{ mod } 3$$ $$x \equiv 5 \text{ mod } 7$$

This yields $x = 236$. We can verify this is correct by observing that $15^{236} \equiv 131 \text{ mod } 337$.

$\endgroup$
  • 1
    $\begingroup$ $q^e$ is a factor of $p$ or $p-1$? $\endgroup$ – 111 Dec 2 '17 at 15:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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