Hensel Lifting

Purpose: Given a root of a polynomial modulo $p$, lift it to a root modulo $p^k$ — doubling the precision each step. The $p$-adic analogue of Newton’s method.

Hensel’s Lemma

Let $f\in \mathbb{Z}[x]$ and suppose $f(r)\equiv 0(\mathrm{mod}{p}^k)$ with $f^{\prime }(r)\not\equiv 0(\mathrm{mod}p)$ (a simple root). Then there is a unique lift $r^{\prime }\mathrm{mod}{p}^{2k}$ with $f(r^{\prime })\equiv 0(\mathrm{mod}{p}^{2k})$, given by

$r^{\prime }=r-f(r)\cdot (f^{\prime }(r){)}^{-1}(\mathrm{mod}{p}^{2k}).$

This is exactly Newton’s iteration $r^{\prime }=r-f(r)/f^{\prime }(r)$, with the inverse taken modulo $p^{2k}$.

The linear (slower but simpler) version lifts one power at a time:
$r_{k+1}=r_k-f(r_k)\cdot (f^{\prime }(r_1){)}^{-1}(\mathrm{mod}{p}^{k+1}).$

Code

// lift a root of f mod p to a root mod p^k, quadratic version
long long henselLift(function<long long(long long,long long)> f,
                     function<long long(long long,long long)> df,
                     long long r, long long p, int k) {
    long long mod = p;
    while (mod < ipow(p, k)) {
        long long nmod = mod * mod;                    // double the precision
        long long inv  = modinv(df(r, nmod), nmod);    // f'(r) is a unit
        r = ((r - f(r, nmod) % nmod * inv) % nmod + nmod) % nmod;
        mod = nmod;
    }
    return r % ipow(p, k);
}

Complexity

Each step doubles the precision, so reaching $p^k$ takes $O(\log k)$ iterations. With naive arithmetic on $O(k\log p)$-bit numbers the total is $O(M(k\log p))$ where $M$ is the multiplication cost — the same asymptotic as a single multiplication at full precision.

Why It Works

Write $r^{\prime }=r+t{p}^k$. Taylor-expand:
$f(r+t{p}^k)\equiv f(r)+t{p}^k{f}^{\prime }(r)(\mathrm{mod}{p}^{2k})$
(all higher terms carry $p^{2k}$). Since $p^k\mid f(r)$, dividing by $p^k$ gives
$\frac{f(r)}{p^k}+t{f}^{\prime }(r)\equiv 0(\mathrm{mod}{p}^k),$
which has a unique solution for $t$ precisely because $f^{\prime }(r)$ is invertible mod $p$. ∎

Singular roots

If $f^{\prime }(r)\equiv 0(\mathrm{mod}p)$, the lemma does not apply. The root may lift in several ways, in one way, or not at all — you must branch over the $p$ candidate lifts and test each.

Worked example: square roots mod $2^k$

To solve $x^2\equiv a(\mathrm{mod}{2}^k)$, note $f^{\prime }(x)=2x$ is never a unit mod 2, so plain Hensel fails. The fix is a specialised iteration $x\leftarrow x(3-a{x}^2)/2$ or a direct bit-by-bit lift — a standard reminder that $p=2$ needs care.

Variants / Use Cases

• Modular square roots mod $p^k$ — solve mod $p$ with Tonelli-Shanks, then lift
• Solving $f(x)\equiv 0(\mathrm{mod}n)$ for composite $n$ — factor $n$, solve each prime power by lifting, recombine with CRT
• Polynomial factorisation over $\mathbb{Z}$ — factor mod a small prime, Hensel-lift to a large prime power, then recombine factors
• $p$-adic numbers — Hensel’s lemma is the statement that ${\mathbb{Z}}_p$ is “complete enough” for Newton’s method
• Newton iteration for formal power series — the exact same lifting idea with $x$ in place of $p$: series inverse, log, exp and sqrt are all Hensel lifts