Pohlig-Hellman algorithm

Question

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.

Answer 1

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