I am using the Pohlig-Hellman algorithm to solve a Discrete Log Problem to find $x$ in
$$3^x = 5 \pmod{113}$$
Using the notation:
$$g^x = h \pmod p$$
We have
$g = 3$, $h = 5$, $p = 113$,
$N = p - 1 = 112 = \prod_{i=1}^{n} q_i^{e_i} = q_1^{e_1} \cdot q_2^{e_2} = 2^4 \cdot 7^1 $
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 & 40 & 42 & \mbox{Calculation I = ?}\\ \hline 7 & 1 & ... & ... & \mbox{...}\\ \hline \end{array}$$
I am only interested in $q=2$ and $e=4$ for this question.
Calculation I:
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 $(40)^x = 42 \pmod {113}$ for $x_0, x_1, x_2, x_3$.
Method 1 - J. Hoffstein, J Piper, J. H. Silverman
$x_0: (40^{2^3})^{x_0} = 112^{x_0} = 42^{2^3} = 112 \pmod {113} \implies (112)^{x_0} = 112 \pmod{113} \implies x_0 = 1$
$x_1: (40^{2^3})^{x_1} = 112^{x_1} = (42 \times 40^{-x_0})^{2^2} \pmod {113} \implies (112)^{x_1} = 112 \pmod{113} \implies x_1 = 1$
Continuing this method I find $x_2=0$ and $x_3=0$.
Method 2 - $\frac{p-1}{q}$
https://youtu.be/BXFNYVmdtJU https://www.cryptologie.net/article/196/pohlig-hellman-algorithm/
$\beta = 42$, $\alpha=40$.
$x_0: q=2^1, \beta^{\frac{p-1}{q}}=\alpha^{\frac{p-1}{q}x_0}. \implies x_0=1$.
$x_1: q=2^2, \beta_1^=\beta \times \alpha^{-x_0}.\implies \beta_1=18. \implies \beta_1^{\frac{p-1}{q}}=\alpha^{\frac{p-1}{q}x_1}. \implies x_1=2$.
Continuing this with this method I find $x_2=0$ and $x_3=0$.
Hence for Method 1 I get $(x_0, x_1, x_2, x_3)=(1, 1, 0, 0)$ but for Method 2 I get $(1, 2, 0, 0)$
I'm struggling to see where I'm going wrong in my working re $x_1$.