# Hensel Lifting

Define $R_q = (\mathbb Z / q \mathbb Z)[x]$. Suppose $f(x)\ g(x) \equiv 1 \pmod{R_q}$. How to "lift" the solution $f(x)$ to find the inverse of $g(x)$ in $R_{q^2}$?

The key is to notice that $[f(x)\ g(x) - 1]^2 \equiv 0 \pmod{R_{q^2}}$, due to

$$f(x)\ g(x) \equiv 1 \pmod{R_q} \; \Rightarrow \; f(x)\ g(x) = 1 + q\ h(x) \; \text{ for some } h(x) \in R_q,$$

This yields us

$$\begin{aligned}
f(x)^2\ g(x)^2\ -2f(x)\ g(x) & \equiv -1 \\
g(x) [ \underline{2f(x) - f(x)^2\ g(x)} ] & \equiv 1 & \pmod{R_{q^2}}
\end{aligned}$$

So the inverse under $R_{q^2}$ is $2f(x) - f(x)^2\ g(x)$.

The process can be thought as an analogy to Newton's method. To see this, define $F(y) = 1/y - g$. We want to "approximate" the solution of $F(y)$ from the initial guess $f$: $$
F(f_1) = F(f) + (f_1 - f) F'(f) + \mathcal{O}(f^2),$$

Newton's method tells us that the linear approximation is $$\begin{aligned}
f_1 & = f - \frac{F(f)}{F'(f)} \\
& = f - \frac{1/f-g}{-1/f^2} \\
& = 2f - f^2 g.
\end{aligned}
$$

## Reference

* https://brilliant.org/wiki/hensels-lemma/