Back to Number Theory Dsa

Quadratic Residues & Modular Roots

September 22, 2026 Wasil Zafar 7 min read

Determine and construct modular roots.

Table of Contents

  1. Intuition, Vocabulary and Foundations
  2. Step-by-Step Derivations and Algorithms
  3. Implementation, Complexity and Engineering
  4. Applications, Case Studies and Exercises

Intuition, Vocabulary and Foundations

Squaring modulo $m$ folds integers into residue classes. Modulo $7$, the nonzero squares are $1$, $2$, and $4$, so $x^2\equiv2\pmod7$ has roots $3$ and $4$, while $x^2\equiv3\pmod7$ has none. For an odd prime $p$, Euler's criterion states

$$a^{(p-1)/2}\equiv1\pmod p$$

for a nonzero quadratic residue and $-1$ for a nonresidue. The Legendre symbol records the three outcomes $-1$, $0$, and $1$. The Jacobi symbol extends the notation multiplicatively to odd composite denominators, but a Jacobi value of $1$ does not guarantee a root: $\left(\frac2{15}\right)=1$, yet $2$ is not a square modulo $15$.

Euler's criterion and Tonelli-Shanks require an odd prime modulus. For composites, solve every prime-power component, combine with CRT, and verify each candidate by checking $r^2\bmod m=a\bmod m$.

ConceptDefinitionExampleBoundaryQuestion answered
Quadratic residue$a\equiv x^2\pmod m$$2\equiv3^2\pmod7$$3$ is a nonresidue modulo $7$Does a root exist?
Legendre symbolPrime-modulus status in $\{-1,0,1\}$$\left(\frac27\right)=1$Denominator must be an odd primeIs $a$ a prime-field square?
Jacobi symbolProduct over odd prime factors$\left(\frac2{15}\right)=1$Value $1$ is inconclusiveCan a composite candidate be rejected?
Tonelli-ShanksIteratively reduces a power-of-two orderRoots of $10$ modulo $13$ are $6,7$Prime-only algorithmHow is a root constructed?
CRT combinationCombines roots for coprime factorsFour roots of $4$ modulo $15$Prime powers require lifting firstHow are local roots combined?

Step-by-Step Derivations and Algorithms

For an odd prime $p$, normalize $a$. Return $0$ when $a=0$ and reject when Euler's criterion gives $-1$. If $p\equiv3\pmod4$, compute $r=a^{(p+1)/4}$. Otherwise factor $p-1=q2^s$ with odd $q$, choose a nonresidue $z$, and initialize

$$c=z^q,\qquad r=a^{(q+1)/2},\qquad t=a^q\pmod p.$$

Tonelli-Shanks maintains $r^2\equiv at\pmod p$. Each iteration finds the least $i$ with $t^{2^i}=1$ and updates by a power of $c$, strictly decreasing the order bound until $t=1$. Cipolla instead exponentiates in a quadratic extension field. For a factored composite, solve each prime-power modulus and enumerate CRT combinations of local roots.

Quadratic Residues & Modular Roots algorithm map
flowchart TD
    A["Normalize a modulo m"] --> B{"Modulus domain?"}
    B -->|"Odd prime"| C["Euler criterion"]
    C --> D{"Residue?"}
    D -->|"No"| E["No roots"]
    D -->|"Yes"| F["Shortcut or Tonelli-Shanks"]
    B -->|"Prime power"| G["Valuation and lifting"]
    B -->|"Factored composite"| H["Solve local factors"]
    G --> H
    H --> I["CRT combinations"]
    F --> J["Verify roots"]
    I --> J

Tonelli-Shanks preserves $r^2\equiv at\pmod p$ while decreasing the exponent bound on the order of $t$; reaching $t=1$ proves correctness. Composite solving is output-sensitive because independent local sign choices can produce exponentially many roots.

Implementation, Complexity and Engineering

This reference supports odd primes and square-free products of supplied distinct odd primes. It rejects repeated factors rather than pretending that prime-power lifting is identical to the prime case, and it verifies all results.

from itertools import product
from math import gcd

def is_prime(n):
    if n < 2: return False
    if n % 2 == 0: return n == 2
    d = 3
    while d <= n // d:
        if n % d == 0: return False
        d += 2
    return True

def legendre(a, p):
    if p == 2 or not is_prime(p): raise ValueError("odd prime required")
    a %= p
    if a == 0: return 0
    v = pow(a, (p - 1) // 2, p)
    return -1 if v == p - 1 else v

def tonelli_shanks(a, p):
    if p == 2: return a % 2
    if not is_prime(p): raise ValueError("prime required")
    a %= p
    if a == 0: return 0
    if legendre(a, p) != 1: return None
    if p % 4 == 3: return pow(a, (p + 1) // 4, p)
    q, s = p - 1, 0
    while q % 2 == 0: q, s = q // 2, s + 1
    z = 2
    while legendre(z, p) != -1: z += 1
    c, r, t, m = pow(z, q, p), pow(a, (q + 1) // 2, p), pow(a, q, p), s
    while t != 1:
        i, probe = 0, t
        while probe != 1:
            probe, i = probe * probe % p, i + 1
        b = pow(c, 1 << (m - i - 1), p)
        r, c, t, m = r * b % p, b * b % p, t * b * b % p, i
    assert r * r % p == a
    return r

def roots_prime(a, p):
    r = tonelli_shanks(a, p)
    return [] if r is None else sorted({r, (-r) % p})

def inverse(a, m):
    return pow(a, -1, m)

def crt_pair(a, m, b, n):
    if gcd(m, n) != 1: raise ValueError("coprime moduli required")
    x = (a + m * (((b - a) * inverse(m, n)) % n)) % (m * n)
    return x, m * n

def roots_square_free(a, factors):
    if not factors or len(set(factors)) != len(factors):
        raise ValueError("distinct factors required")
    if any(p == 2 or not is_prime(p) for p in factors):
        raise ValueError("distinct odd primes required")
    local = [roots_prime(a, p) for p in factors]
    if any(not roots for roots in local): return []
    modulus = 1
    for p in factors: modulus *= p
    result = set()
    for choice in product(*local):
        x, current = choice[0], factors[0]
        for residue, p in zip(choice[1:], factors[1:]):
            x, current = crt_pair(x, current, residue, p)
        assert x * x % modulus == a % modulus
        result.add(x)
    return sorted(result)

if __name__ == "__main__":
    assert roots_prime(2, 7) == [3, 4]
    assert roots_prime(10, 13) == [6, 7]
    assert roots_prime(3, 7) == []
    assert roots_square_free(4, [3, 5]) == [2, 7, 8, 13]
    assert roots_square_free(2, [3, 5]) == []
    print("all tests passed")
MethodDomainTime profileOutputFailure modeMitigation
Exhaustive searchSmall positive modulus$O(m)$All rootsToo slow for large $m$Use as a test oracle
Euler criterionOdd primeOne exponentiationExistence onlyComposite inputValidate primality
Jacobi symbolPositive odd modulus$O(\log n)$Filter onlyTreating $1$ as proofSolve factors explicitly
Tonelli-ShanksOdd primePolylogarithmic modular workOne root, then negateBroken order updateVerify the candidate
CipollaOdd prime$O(\log p)$ extension multiplicationsOne root, then negateFaulty pair arithmeticUnit-test field operations
Prime-power liftingPrime powerValuation-dependentVariable multiplicityAssuming unique liftingSeparate divisible cases
CRT enumerationCoprime solved factorsOutput-sensitiveAll combined rootsDuplicate resultsNormalize, verify, deduplicate

Applications, Case Studies and Exercises

Modular roots occur in computational number theory and cryptographic constructions. A reliable API must expose whether its modulus is prime, a known prime power, or an already factored composite.

Practice

Apply Quadratic Residues & Modular Roots

Prime case: Solve $x^2\equiv10\pmod{13}$. Euler's criterion confirms existence; Tonelli-Shanks returns $6$, and the paired root is $7$. Verify both squares.

Composite case: Solve $x^2\equiv4\pmod{15}$. Local roots are $1,2$ modulo $3$ and $2,3$ modulo $5$. CRT gives $2,7,8,13$.

Hands-on challenge: Compare the solver with exhaustive search for every odd modulus up to $500$. Test zero, negative inputs, nonresidues, repeated factors, and mislabeled composites. Success requires sorted unique outputs and exact verification.

Exercises: list residues modulo $11$; evaluate $\left(\frac5{11}\right)$; trace Tonelli-Shanks for $5$ modulo $41$; explain why Jacobi value $1$ is inconclusive; implement Cipolla; extend the solver to odd prime powers.

Use Legendre or Euler for prime-field existence, Tonelli-Shanks or Cipolla for construction, valuation-aware lifting for prime powers, and CRT for factored composites. Never use a Jacobi value of $1$ as a composite existence proof, and verify every returned root.

Next in the Series

In Groups, Primitive Roots & Discrete Logarithms, we'll explore Reason about modular operations through finite-group structure..

Continue the Series

Modular Arithmetic & Fast Exponentiation

Compute safely and efficiently in residue classes.

Read Article
Primes, Factorization & Divisor Structure

Understand prime structure and enumerate multiplicative objects efficiently.

Read Article