Modular square root calculator

How it works

Modulo an odd prime $p$, a nonzero $a$ has either two square roots $\pm x$ or none, and Euler’s criterion tells which. When $p \equiv 3 \pmod 4$ the root is simply $a^{(p+1)/4}$. In general the Tonelli-Shanks algorithm writes $p - 1 = Q \cdot 2^S$ and uses a non-square $z$ to correct a first guess $a^{(Q+1)/2}$ step by step, halving the order of the error term $t$ each round.

For composite $n$ one solves modulo each prime power separately: a root modulo $p$ is lifted to $p^k$ by Hensel’s lemma (a Newton step), powers of 2 follow their own rules, and the Chinese remainder theorem glues the pieces together. With $k$ distinct odd prime factors there are $2^k$ roots, so modulo $n = pq$ a square has four.

Without the factorization this is as hard as factoring: from two roots $x, y$ with $x \not\equiv \pm y$ one gets the factor $\gcd(x - y, n)$. Rabin’s cryptosystem is built on exactly this, and square roots modulo primes are used to find points on elliptic curves.