We use essential cookies to run the site (session, security, and your theme/language preferences). With your permission we also load embedded third-party content, such as YouTube videos. Cookie Policy
Turning one good guess mod p into an exact answer mod p^k
Author(s):Elier Rodríguez García
Index
Introduction
Suppose you want a square root of 2, but only working modulo a prime p. Mod 7, that's easy: 32=9≡2(mod7). So x=3 solves x2≡2(mod7).
Now raise the stakes: can you solve x2≡2(mod49)? Mod 2401 (74)? You could search by brute force, but there is a much sharper tool. Hensel lifting takes the solution you already have mod p and repairs it into a solution mod p2, then mod p4, then mod p8 — with the number of correct "digits" (in base p) roughly doubling at every step.
It is, quite literally, Newton's method transplanted from real numbers into the world of modular arithmetic — and it is one of the workhorses behind how computers factor polynomials and reason about numbers modulo prime powers.
Watch a Root Sharpen
Below, x=3 already solves x2≡2(mod7). Press Lift one step and watch the same root get promoted to a solution modulo 72, then 74, then 78 — each click roughly doubles how many base-7 digits of the true 2-like value are locked in.
<p class="hint">We start from a solved congruence — <b>x = 3</b> satisfies x² − 2 ≡ 0 (mod 7). Each click of <b>Lift one step</b> runs one Newton-style correction that promotes the root to the next modulus, roughly doubling the exponent of 7 each time.</p>
<div class="stage">
<div class="row"><span class="lbl">Modulus:</span><span id="modulus" class="val">7</span></div>
<div class="row"><span class="lbl">Root x:</span><span id="root" class="val">3</span></div>
<div class="row"><span class="lbl">Check:</span><span id="check" class="val">x² − 2 ≡ 0</span></div>
</div>
<div class="ladder" id="ladder"></div>
<div class="status" id="status">Ready to lift — press the button to double the precision.</div>
<div class="btns">
<button id="lift" type="button">Lift one step</button>
<button id="reset" type="button" class="ghost">Reset</button>
</div>
const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Goal: refine the root x=3 of x^2-2 mod 7 into a root mod 7^2, 7^4, 7^8, 7^16.
// Method: Hensel's lemma / Newton's method for congruences, one doubling step at a time.
const P = 7n;
const MAX_STEPS = 4; // cap the demo at 4 lifting steps (mod 7^16)
// Extended Euclidean algorithm, used to compute modular inverses.
function egcd(a, b) {
if (b === 0n) return [a, 1n, 0n];
const [g, x, y] = egcd(b, a % b);
return [g, y, x - (a / b) * y];
}
function modinv(a, m) {
a = ((a % m) + m) % m;
const [g, x] = egcd(a, m);
if (g !== 1n) return null; // no inverse exists (should not happen here since f'(x0) is not divisible by p)
return ((x % m) + m) % m;
}
// Demo state, kept between clicks.
let k = 1; // current exponent k, so the current modulus is 7^k
let x = 3n; // current root, valid modulo 7^k
let steps = 0;
function f(v, mod) { return ((v * v - 2n) % mod + mod) % mod; } // f(x) = x^2 - 2, reduced modulo the given modulus
function henselStep() {
const pk2 = P ** BigInt(2 * k); // the modulus we are lifting to this step, 7^(2k)
const fx = f(x, pk2);
const fpInv = modinv(2n * x, pk2); // inverse of f'(x) = 2x modulo the target modulus
let xNew = x - fx * fpInv;
xNew = ((xNew % pk2) + pk2) % pk2;
x = xNew;
k = 2 * k;
}
function render() {
const modulus = P ** BigInt(k);
document.getElementById('modulus').textContent = modulus.toString();
document.getElementById('root').textContent = x.toString();
const residue = f(x, modulus);
document.getElementById('check').textContent = 'x² − 2 ≡ ' + residue.toString() + ' (mod ' + modulus.toString() + ')';
const ladder = document.getElementById('ladder');
const entry = document.createElement('div');
entry.className = 'step';
entry.innerHTML = '<span class="mod">7^' + k + ' = ' + modulus.toString() + '</span><span class="x">x = ' + x.toString() + '</span>';
ladder.appendChild(entry);
}
function setStatus(t, cls) {
const s = document.getElementById('status');
s.textContent = t;
s.className = 'status ' + cls;
}
function lift() {
if (steps >= MAX_STEPS) return;
henselStep();
steps++;
render();
if (steps >= MAX_STEPS) {
setStatus(i18nFmt('Done — root is now exact modulo %mod% after 4 lifts.', { mod: (P ** BigInt(k)).toString() }), 'done');
document.getElementById('lift').disabled = true;
} else {
setStatus(i18nFmt('Lifted! Now exact modulo %mod%.', { mod: (P ** BigInt(k)).toString() }), 'ok');
}
}
function reset() {
k = 1;
x = 3n;
steps = 0;
document.getElementById('ladder').innerHTML = '';
document.getElementById('lift').disabled = false;
render();
setStatus('Ready to lift — press the button to double the precision.', '');
}
document.getElementById('lift').addEventListener('click', lift);
document.getElementById('reset').addEventListener('click', reset);
render();
Result
Console
Notice what never happens: the algorithm never throws away the previous answer and starts over. It reuses the current root x, computes how wrong f(x)=x2−2 still is, and nudges x by an amount that cancels that error modulo a much larger power of p. That reuse is exactly what makes lifting so fast compared to searching from scratch at each new modulus.
The Real Complexity
Hensel lifting is a solved, constructive method — there is no open question here, just a beautiful piece of 20th-century algebra due to Kurt Hensel (1897, 1904). Here is why it works and why it is fast.
The starting condition. You need a simple root: some x0 with f(x0)≡0(modp) and f′(x0)≡0(modp) (the derivative doesn't vanish). That non-vanishing derivative is what guarantees the root can be lifted uniquely at every stage.
The lifting step. Given a root xk valid modulo pk, define
xk+1=xk−f(xk)⋅f′(xk)−1(modp2k)
where the inverse of f′(xk) is taken modulo p2k (it exists precisely because f′(x0)≡0(modp)). This is exactly Newton's update rule x−f(x)/f′(x), just computed with modular inverses instead of real division.
Quadratic convergence. If f(xk)≡0(modpk), a short Taylor-expansion argument shows f(xk+1)≡0(modp2k). The precision doubles every step: p→p2→p4→p8→… — reaching p1024 takes only about ten steps, not a thousand.
Cost per step. Each lift is one polynomial evaluation plus one modular inverse computed via the extended Euclidean algorithm — cheap, and independent of how large the target modulus eventually gets.
The one thing lifting cannot do is manufacture a root that isn't there: if f has no root mod p, or the derivative vanishes at every root (a repeated root), the simple version of the lemma does not apply and a more delicate analysis is needed.
Where It Matters
Lifting a solution instead of re-deriving it from nothing shows up anywhere numbers modulo a prime power need to be pinned down precisely:
Polynomial factorization. The Zassenhaus and later LLL-based factoring algorithms first factor a polynomial modulo a small prime p — cheap and reliable — then Hensel-lift that factorization to modulo pk for k large enough to reconstruct the true integer factors.
p-adic numbers. A compatible sequence of roots mod p,p2,p4,…is, by construction, a single p-adic number — Hensel's lemma is the classical tool for showing an equation has a solution in Zp.
Cryptography and coding theory. Arithmetic over rings Z/pkZ appears in some lattice-based and code-based schemes, where lifting square roots or inverses through increasing powers of p avoids recomputing from scratch.
Numerical algorithms in computer algebra. Whenever an exact integer or rational answer is reconstructed from modular data (rational reconstruction, Gröbner basis computations), lifting through prime powers is the standard way to get enough precision cheaply.
It's the same idea as Newton's method for real roots, just replaying inside modular arithmetic instead of the real line.
Conclusion
Hensel lifting turns a single lucky guess modulo a prime into an entire tower of increasingly precise answers, each one built cheaply from the last. No brute-force search modulo p100 is ever needed — just repeated applications of the same tiny Newton-style correction.
It is a quiet reminder that "solved modulo a small number" and "solved exactly" are sometimes only a handful of doubling steps apart, the same spirit that drives Newton's method everywhere else in computation.
Comments
Loading comments...