Quadratic Residues

$a$ is a quadratic residue modulo $p$ if $x^2\equiv a$ has a solution. For an odd prime $p$, exactly $\frac{p-1}{2}$ of the non-zero residues are quadratic residues.

Euler’s criterion

$a^{\frac{p-1}{2}}\equiv \{\begin{array}{ll}+1& a\text{ is a QR}\\ -1& a\text{ is a non-residue}\\ 0& p\mid a\end{array}(\mathrm{mod}p).$

int legendre(long long a, long long p) {
    a %= p; if (a < 0) a += p;
    if (a == 0) return 0;
    return powmod(a, (p - 1) / 2, p) == 1 ? 1 : -1;
}

$O(\log p)$ — this is the Legendre symbol $\left(\frac{a}{p}\right)$.

The Legendre symbol’s rules

Rule
Multiplicative	$\left(\frac{ab}{p}\right)=\left(\frac{a}{p}\right)\left(\frac{b}{p}\right)$
$\left(\frac{-1}{p}\right)$	$+1$ iff $p\equiv 1(\mathrm{mod}4)$
$\left(\frac{2}{p}\right)$	$+1$ iff $p\equiv \pm 1(\mathrm{mod}8)$
$\left(\frac{a}{p}\right)$ depends only on $a\mathrm{mod}p$

QR × QR = QR, QR × NR = NR, NR × NR = QR — the residues form an index-2 subgroup.

Quadratic reciprocity

For distinct odd primes $p,q$:

$\left(\frac{p}{q}\right)\left(\frac{q}{p}\right)=(-1{)}^{\frac{p-1}{2}\cdot \frac{q-1}{2}}.$

In words: $\left(\frac{p}{q}\right)=\left(\frac{q}{p}\right)$ unless both $p\equiv q\equiv 3(\mathrm{mod}4)$, in which case they differ in sign.

Combined with the supplementary rules, this gives a Euclidean-style $O({\log }^2)$ algorithm for the Jacobi symbol that needs no exponentiation:

int jacobi(long long a, long long n) {            // n odd positive
    a %= n; if (a < 0) a += n;
    int result = 1;
    while (a) {
        while (a % 2 == 0) {
            a /= 2;
            if (n % 8 == 3 || n % 8 == 5) result = -result;
        }
        swap(a, n);
        if (a % 4 == 3 && n % 4 == 3) result = -result;
        a %= n;
    }
    return n == 1 ? result : 0;
}

Jacobi vs Legendre

The Jacobi symbol $\left(\frac{a}{n}\right)$ extends the Legendre symbol to odd composite $n$ by multiplying the Legendre symbols of $n$‘s prime factors.

Jacobi $=1$ does not mean $a$ is a QR

For composite $n$, $\left(\frac{a}{n}\right)=+1$ can happen when $a$ is a non-residue modulo two prime factors. Only $-1$ is conclusive (it proves $a$ is a non-residue). This asymmetry is the basis of the Solovay-Strassen primality test.

Finding the square root

Case	Method	Cost
$p\equiv 3(\mathrm{mod}4)$	$x=a^{(p+1)/4}$	$O(\log p)$
$p\equiv 5(\mathrm{mod}8)$	a short closed form	$O(\log p)$
general $p$	Tonelli-Shanks	$O({\log }^{2}p)$
general $p$, $p-1$ has a big $2^k$	Cipolla	$O(\log p)$
$p^e$	solve mod $p$, Hensel lift	$O({\log }^{2}p)$
$2^e$	special bit-by-bit lifting	$O(e)$
composite $n$	factor, solve per prime power, CRT	as hard as factoring

That last row is the crux of Rabin cryptography: computing square roots modulo a composite is equivalent to factoring it.

Counting solutions

$x^2\equiv a(\mathrm{mod}p)$ has $1+\left(\frac{a}{p}\right)$ solutions: two if $a$ is a QR, one if $a=0$, zero otherwise.

Modulo $n=\prod p_i^{e_i}$ (odd primes), the count is $\prod \left(1+\left(\frac{a}{p_i}\right)\right)$ — so $2^k$ solutions when $a$ is a residue modulo all $k$ distinct primes. Powers of 2 contribute up to 4.

Where it appears

Problem	Use
Solve $x^2\equiv a(\mathrm{mod}p)$	Tonelli-Shanks
Count solutions of a quadratic congruence	Legendre symbol
Sum of two squares ($n=x^2+y^2$)	needs $\sqrt{-1}$, then Cornacchia
Elliptic curve point decompression	recover $y$ from $x$
Solovay-Strassen primality test	Jacobi vs Euler criterion
Counting points on a conic mod $p$	character sums
Is $n$ a perfect square?	quick filter: check $n\mathrm{mod}64$ and $n\mathrm{mod}63$ before taking a root

The perfect-square filter

bool maybeSquare(long long n) {
    static bool ok[64] = {}; // precompute squares mod 64
    return ok[n & 63];
}

Only 12 of the 64 residues mod 64 are squares, so this rejects 81% of non-squares in one instruction — a useful speedup inside tight loops.

See also: Tonelli-Shanks · Cipolla · Discrete Root