Engineering / Mathematics — Quadratic Residues
Computing Modular Square Roots: Prime Power Modulus
Lifting a square root from a prime to a prime power by Hensel's method, and the special handling powers of two require.
Executive summary
A square root modulo a prime lifts to a root modulo any power of that prime by Newton iteration on the integers, doubling the precision at each step.
Powers of two need separate treatment because the derivative of the squaring map vanishes modulo two, which is exactly the condition Hensel's lemma excludes.
Learning objectives
- State Hensel's lemma for square roots.
- Execute the lifting iteration.
- Handle the exceptional case of powers of two.
01Hensel lifting
Hensel's lemma for square roots
Let p be an odd prime and suppose x₀² ≡ a (mod p^k) with p ∤ a. Then
x₁ = x₀ − (x₀² − a) · (2x₀)^{−1} satisfies x₁² ≡ a (mod p^{2k}).
This is Newton's method applied to f(x) = x² − a, with the derivative 2x invertible because p is odd and x is coprime to p. The precision doubles at each iteration, so reaching p^e takes logarithmically many steps.
Lift a square root to p^e
odd prime p, exponent e, residue a coprime to px with x² ≡ a (mod p^e)- Compute x₀ with x₀² ≡ a (mod p) by the prime-modulus method.
- Set k = 1.
- While k < e:
- Compute the inverse of 2x modulo p^{min(2k, e)}.
- Update x = x − (x² − a)(2x)⁻¹, reduced mod p^{min(2k, e)}.
- Set k = min(2k, e).
- Return x.
O(log e) iterations, each a modular inversion and multiplication02The obstruction at two
The correct statement for powers of two follows the residue structure. An odd a is a square modulo 2^e for e ≥ 3 exactly when a ≡ 1 (mod 8), and then it has four square roots rather than two.
| Modulus | Condition on odd a | Number of roots |
|---|---|---|
| 2 | always | 1 |
| 4 | a ≡ 1 (mod 4) | 2 |
| 2^e, e ≥ 3 | a ≡ 1 (mod 8) | 4 |
Roots modulo powers of two are constructed by a direct bit-by-bit lifting that adds one bit of precision per step rather than doubling, compensating for the failed Newton iteration.
03Why lifting matters
Composite moduli
Roots modulo a composite are assembled from roots modulo each prime power, so lifting is a required subroutine.
p-adic methods
The same iteration computes square roots in the p-adic integers, where it converges rather than terminating.
Polynomial analogue
Hensel lifting for polynomials underlies factorisation over the integers: factor modulo a small prime, then lift to a high power and recover the integer factors.
04Frequently asked questions
Why does the precision double rather than increase by one?
Because Newton's method converges quadratically. The error term is squared at each step, so the number of correct digits doubles — the same behaviour as Newton's method over the reals.
What if a is divisible by p?
The lemma does not apply, and the root involves a power of p factored out first. Writing a = p^{2m}b with b coprime to p reduces to the coprime case, and an odd power of p means no root exists.
Is the inverse recomputed at every step?
It can be updated by the same Newton iteration rather than recomputed, which is what efficient implementations do — inverting once at low precision and lifting the inverse alongside the root.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 295-296.
This page carries the durable method layer only: definitions, constructions, algorithms, complexity results and selection criteria, authored originally for KEVOS. No text is transcribed or paraphrased from the source, and no numeric tables or benchmark data are reproduced — these are routed to live authoritative sources instead.
Author: Kevin Jogin. Last reviewed 2026-08-07.