## Overview
Cho các số $p$ và $e >= 1$, nếu $x$ là nghiệm của phương trình $f(x) \equiv 0 \pmod {p^e}$. Khi đó $x$ cũng là nghiệm của $f(x) \equiv 0 \pmod {p}$. (dễ c/m)

Do đó, để giải nghiệm của pt $f(x) \equiv 0 \pmod {p^e}$ đầu tiên ta cần tìm nghiệm của $f(x) \equiv 0 \pmod {p}$. Sau đó là tìm tiếp các nghiệm $p^2, p^3, \cdots$

Để giải quyết vấn đề này ta đã có giải pháp là sử dụng **hensel's lemma**.

## Hensel's lemma
**Ref:** https://zhuanlan.zhihu.com/p/636849796

Cho $f(x)$ là một phường trình với các hệ số nguyên, và $e \ge 2$. Gọi $r$ là nghiệm của phương trình $f(x) \equiv 0 \pmod {p^{e-1}}$ khi đó:
- Nếu $f'(r) \not \equiv 0 \pmod p$ thì tồn tại một giá trị $t$, $0 \leq t < p$ thỏa mãn:
$$ f(r + t*p^{e-1}) \equiv 0 \pmod {p^e}$$
- Nếu $f'(r) \equiv 0 \pmod p$ và $f(r) \equiv 0 \pmod {p^e}$, khi đó với $\forall t \in \mathbb{Z}$ ta có:
$$f(r + t*p^{e-1}) \equiv 0 \pmod {p^e}$$
- Nếu $f'(r) \equiv 0 \pmod p$ và $f(r) \not \equiv 0 \pmod {p^e}$, khi đó: $f(x) \equiv 0 \pmod {p^e}$ không tồn tại $t$ thỏa mãn.

## Chứng minh
Với $r$ là nghiệm của phường trình $f(x) \equiv 0 \pmod {p^{e-1}}$ suy ra $p^{e-1} \vert f(r)$. Nên $r + t*p^{e-1}$ cũng là nghiệm của phương trình $f(x) \equiv 0 \pmod {p^{e-1}}$.

Chúng ta cần tìm $t$ thỏa mãn điều kiện:
$$f(r + t*p^{e-1}) \equiv 0 \pmod {p^e}$$

Khai triển Taylor:
\begin{align*}
f(r + t p^{e-1})
&= f(r) + f'(r)t p^{e-1} + \cdots + \frac{f^{(n)}(r)}{n!}(t p^{e-1})^n \\
&\equiv f(r) + f'(r)t p^{e-1} \pmod{p^e} \\
\Rightarrow\quad
f'(r)t p^{e-1}
&= -f(r) + k p^e, \quad k \in \mathbb{Z}
\end{align*}

Lại có $p^{e-1} \vert f(r)$ suy ra:
\begin{align*}
f'(r)t
&= \frac{-f(r) + k p^e}{p^{e-1}}, \quad k \in \mathbb{Z} \\
\Rightarrow\quad f'(r)t
&= \frac{-f(r)}{p^{e-1}} \pmod p \quad (*)
\end{align*}

- Với $f'(r) \not \equiv 0 \pmod p$, sẽ tồn tại $t$ duy nhất thỏa mãn biểu thức $(*)$:
$$t = \frac{-f(r)}{p^{e-1} * f'(r)} \pmod {p}$$

- Với $f'(r) \equiv 0 \pmod p$ và $f(r) \equiv 0 \pmod {p^e}$, có **vô số** số nguyên $t$ thỏa mãn biểu thức $(*)$ .

- Với $f'(r) \equiv 0 \pmod p$ và $f(r) \not \equiv 0 \pmod {p^e}$, **không tồn tại** $t$ thỏa mãn biểu thức $(*)$.

### Ví dụ:
Tìm nghiệm của phương trình $f(x) = x^3 + x^2 + 4 \equiv 0 \pmod {25}$:
Giải:

Đầu tiên ta sẽ tìm nghiệm của pt $x^3 + x^2 + 4 \equiv 0 \pmod 5$ ta sẽ dễ dàng tìm được nghiệm là $x = 3$.

Áp dụng Hensel's lemma với $r = 3$, $f'(x) = 3x^2 + 2 x$

Ta có $f'(3) = 3* 9 + 2* 3 \equiv 3 \pmod 5$, suy ra:

\begin{align*}
t &= \frac{-f(3)}{5 * f'(3)} \pmod 5 \\
\Rightarrow t &\equiv \frac{-40}{5 * 3}\equiv -8*3^{-1} \equiv 4 \pmod 5
\end{align*}

Vậy ta có nghiệm $x = r + 5*t = 3 + 5*4 = 23$ là nghiệm của phương trình $f(x) = x^3 + x^2 + 4 \equiv 0 \pmod {25}$.

## Implement in sagemath

# https://pypi.org/project/sageball/
def hensel_solve(f, p, r):
  """
  Solves polynomial roots in the ring Zmod(p**r) using Hensel's lifting method.

  Parameters:
  f (polynomial): The polynomial equation.
  p (int): A prime number.
  r (int): The exponent.

  Raises:
  ValueError: If p is not a prime number or if f has no roots.
  """
  if not is_prime(p):
    raise ValueError("p must be a prime")
  f = f.change_ring(Zp(p))
  F = f.change_ring(Zmod(pow(p, r)))
  P = Zp(p, max(30, r))
  Fd = derivative(F)
  origin_roots = f.roots()
  if not len(origin_roots):
    raise ValueError("f has no roots")
  ans = set()
  for x in origin_roots:
    x_k = ZZ(x[0])
    flag = 0
    for k in range(1, r):
      if Fd(x_k) == P(0):
        if Zmod(pow(p, r))(f(x_k)) == 0:
          continue
        else:
          flag = 1
          break
      else:
        x_k = Zmod(pow(p, r))(P(x_k) - P(F(x_k)) / P(Fd(x_k)))
    if not flag:
      ans.update({x_k})
  return list(ans)