Q:

Use Pohlig-Hellman to solve discrete log

We have $$7^x = 166 \pmod{433}$$ 
I need to find $x$ using the Pohlig-Hellman algorithm.

A:

I will assume you have access to a better description of the algorithm than that web site. If not, refer to:

A Course in Number Theory and Cryptography, 2nd Ed., N. Koblitz
An Introduction to Cryptography, R. A. Mollin
An Introduction to Mathematical Cryptography, J. Hoffstein, J. Pipher, J. H. Silverman

We are asked to use the Pohlig-Hellman algorithm to solve a Discrete Log Problem and find $x$ for:
$$7^x = 166 \pmod{433}$$ 
Using the notation:
$$g^x = h \pmod p$$
We have:
$$g = 7, h = 166, p = 433, N = p - 1 = \prod q_i^{e_i} = q_1^{e_1} \cdot q_2^{e_2} = 432 = 2^4 \cdot 3^3$$
We can summarize the necessary algorithm calculations in a handy table as:
$$\begin{array}{|c|c|c|c|c|} \hline
  \large q  & \large e & \large g^{(p-1)/q^e} & \large h^{(p-1)/q^e} & \mbox{Solve}~ \large \left(g^{(p-1)/q^e} \right)^x = ~ \large h^{(p-1)/q^e}~ \mbox{for} ~ \large x \\  \hline
2 & 4 & 265 & 250 & \mbox{Calculation I = ?}\\  
   \hline
3 & 3 & 374 & 335 & \mbox{Calculation II = ?}\\  \hline
\end{array}$$
Calculation I:
We want to solve:
$$x \equiv x_0 + x_1q + \ldots + x_{e-1}q^{e−1} \pmod {2^4} \equiv  x_0 + 2x_1 + 4x_2 + 8x_3 \pmod {2^4}$$

Solve $(265)^x = 250 \pmod {433}$ for $x_0, x_1, x_2, x_3$.
$x_0: (265^{2^3})^{x_0} = 250^{2^3} \pmod {433} \implies (432)^{x_0} = 432 \implies x_0 = 1$
$x_1: (265^{2^3})^{x_1} = (250 \times 265^{-x_0})^{2^2} \pmod {433} = (250 \times 265^{-1})^{2^2} \pmod {433} = (250 \times 250)^{2^2} \pmod {433} \implies (432)^{x_1} = 432 \implies x_1 = 1$
$x_2: (265^{2^3})^{x_2} = (250 \times 265^{-x_0-2x_1})^{2^1} \pmod {433} = (250 \times 265^{-3})^{2^2} \pmod {433} = (250 \times 195)^{2^1} \pmod {433} \implies (432)^{x_2} = 432 \implies x_2 = 1$
$x_3: (265^{2^3})^{x_3} = (250 \times 265^{-x_0-2x_1-4x_2})^{2^0} \pmod {433} = (250 \times 265^{-7})^{2^0} \pmod {433} = (250 \times 168)^{2^0} \pmod {433} \implies (432)^{x_3} = 432 \implies x_3 = 1$

Thus, our first result is:
$$x \equiv x_0 + 2x_1 + 4x_2 + 8x_3 \pmod {2^4} \equiv 1 + 2 + 4 + 8 \pmod {2^4} \equiv 15 \pmod {2^4}$$
Calculation II:
We want to solve:
$$x \equiv x_0 + x_1q + \ldots + x_{e-1}q^{e−1} \pmod {3^3} \equiv  x_0 + 3x_1 + 9x_2 \pmod {3^3}$$

Solve $(374)^x = 335 \pmod {433}$ for $x_0, x_1, x_2$.
$x_0: (374^{3^2})^{x_0} = 335^{3^2} \pmod {433} \implies (234)^{x_0} = 198 \implies x_0 = 2$. Note: you only needed to test $x_0 = 0, 1, 2$, so it is clear which one $x_0$ is.
$x_1: (374^{3^2})^{x_1} = (335 \times 374^{-x_0})^{3^1} \pmod {433} = (335 \times 374^{-2})^{3^1} \pmod {433} = (335 \times 51)^{3^1} \pmod {433} = 1 \pmod{433} \implies (234)^{x_1} = 1 \pmod {433} \implies x_1 = 0$
$x_2: (374^{3^2})^{x_2} = (335 \times 374^{-x_0-3x_1})^{3^0} \pmod {433} = (335 \times 374^{-2})^{3^0} \pmod {433} = (335 \times 51)^{3^0} \pmod {433} = 198 \pmod{433} \implies (234)^{x_2} = 198 \pmod {433} \implies x_2 = 2$. Note: you only needed to test $x_2 = 0, 1, 2$, so it is clear which one $x_2$ is. 

Thus, our second result is:
$$x \equiv x_0 + 3x_1 + 9x_2 \pmod {3^3} \equiv 2 + 0 + 9 \times 2 \pmod {3^3} \equiv 20 \pmod {3^3}$$
Next, we have to use the Chinese Remainder Theorem to solve the simultaneous congruences: 
$$x \equiv 15 \pmod {2^4} , ~~ x \equiv 20\pmod {3^3}$$
This yields:
$$x = 47$$
We check our answer by computing:
$$7^{47} = 166 \pmod {433} ~~ \checkmark$$

