Modular Square Roots (Composite Modulus)

Factorization difficulty depends on the size of the prime factors of n, not just the size of the input. If the factorization is incomplete, no root is claimed; “no solution” can still be certain without it, when the Jacobi symbol of a over a divisor of n is −1 or a prime power already found admits no root. The exact number of solutions is always shown; the solutions themselves are listed when there are at most 1000. Computation runs locally in your browser.

Write n = q₁^k₁ ⋯ q_r^k_r. By the Chinese Remainder Theorem, x² ≡ a (mod n) holds exactly when x² ≡ a (mod q_i^k_i) for every i, so the solutions are the CRT combinations of the solutions modulo the prime powers, and their number is the product of the component counts.

Odd prime power q^k, with a ≢ 0 and q\nmid a: solvable exactly when (a/q) = 1. A root modulo q is found as on the prime-modulus page and lifted to q^{k} by Hensel's lemma (Newton's step x ↦ x − (x² − a)/(2x) modulo q^{j+1}). There are exactly two roots, ±y.

Powers of 2. For odd a: modulo 2 there is one root; modulo 4, x^{2}\equiv a is solvable iff a ≡ 1 (mod 4) (roots 1 and 3); modulo 2^{k}, k\ge 3, iff a ≡ 1 (mod 8), with four roots ±y, ±y + 2^(k−1).

When q divides a. If a\equiv 0\pmod{q^{k}}, then x^{2}\equiv 0 iff q^⌈k/2⌉ | x, giving q^⌊k/2⌋ roots. Otherwise let v be the exponent of q in a modulo q^{k}, a = q^v·u. If v is odd there is no root. If v is even, x = q^(v/2)·y with y² ≡ u (mod q^(k−v)), and each root y of that unit problem gives q^(v/2) roots x modulo q^{k}.

Verification. Every listed root x is checked: x² mod n = a mod n. If some prime factor is only a probable prime, roots are still verified, but completeness (and the count) assume that factor is prime.

Related: Modular Square Roots (prime modulus) · Chinese Remainder Theorem · Legendre Symbol · Prime Factorization