Modular Square Roots

Inputs

Integer

a

Any integer.

Odd prime

p

Odd prime greater than 2.

The modulus is checked with the site's primality classifier: below $3.3\times10^{24}$ the answer is exact; above it $p$ is only a probable prime, the returned roots are still verified, but completeness is stated assuming $p$ is prime. Composite moduli are not handled here. Computation runs locally in your browser.

Try

Result

—

Solution steps

—

Method

A square root of $a$ modulo $p$ is a residue $x$ with $x^{2}\equiv a\pmod p$ . The calculator first reduces $a$ modulo $p$ .

Existence and count. The Legendre symbol decides existence: $\left(\frac{a}{p}\right)=-1$ means there is no root, $a\equiv 0$ gives the single root $x\equiv 0$ , and $\left(\frac{a}{p}\right)=1$ gives exactly two roots. Indeed, if $x^{2}\equiv y^{2}\pmod p$ then $p\mid (x-y)(x+y)$ , and since $p$ is prime, $x\equiv \pm y\pmod p$ . So a nonzero residue has exactly the roots $x$ and $p-x$ .

Case p ≡ 3 (mod 4). Then

x\equiv a^{(p+1)/4}\pmod p,\qquad x^{2}\equiv a^{(p+1)/2}=a\cdot a^{(p-1)/2}\equiv a\pmod p,

by Euler's criterion for a quadratic residue $a$ .

Case p ≡ 5 (mod 8). Let $v\equiv a^{(p+3)/8}\pmod p$ . If $v^{2}\equiv a$ then $x=v$ ; otherwise $x\equiv v\,i\pmod p$ with $i\equiv 2^{(p-1)/4}$ , a square root of $-1$ .

General case: Tonelli-Shanks. Write $p-1=Q\cdot 2^{S}$ with $Q$ odd (only factors of 2 are removed; nothing is factored). Find the smallest quadratic nonresidue $z$ and set

c=z^{Q},\qquad x=a^{(Q+1)/2},\qquad t=a^{Q},\qquad M=S.

Then $x^{2}\equiv a\,t\pmod p$ holds from the start. Because $a$ is a residue, $t$ has order a power of 2. While $t\ne 1$ : find the least $i$ , $0<i<M$ , with $t^{2^{i}}\equiv 1$ ; put $b=c^{2^{M-i-1}}$ ; then replace $x$ by $xb$ , $c$ by $b^{2}$ , $t$ by $tb^{2}$ , and $M$ by $i$ . The invariant $x^{2}\equiv a\,t$ is preserved and the 2-power order of $t$ strictly shrinks, so $t$ reaches 1. Then $x^{2}\equiv a\pmod p$ .

Verification. Every returned root $r$ is checked directly: $r^{2}\bmod p=a\bmod p$ . For a probable-prime $p$ each returned root is a verified fact, but "these are all the roots" and "there are no roots" hold only if $p$ is actually prime.

Inputs

Result

Solution steps

Tonelli-Shanks iterations

Method