Find x such that x^2 = a (mod p) for prime modulus p
a (number to sqrt)
p (prime modulus)
Result
Quadratic Residue Status
-
Root 1
-
Root 2
-
Detailed Derivation
Modular Square Root Properties
Find x where x^2 = a (mod p)
Euler: a^((p-1)/2) = 1 if sqrt exists
Two roots: x and p - x
Algorithm: Tonelli-Shanks
A modular square root of a modulo p is a number x such that x^2 = a (mod p). Not all numbers have modular square roots. The Euler criterion determines existence, and the Tonelli-Shanks algorithm efficiently finds the roots.
⚠p must be an odd prime. The algorithm works for small p via trial search. For p=2, sqrt(x) mod 2 = x (trivially).
What Is a Modular Square Root?
A modular square root solves the congruence x^2 = a (mod p). This is a fundamental operation in number theory with applications in cryptography. Numbers with square roots modulo p are called quadratic residues.
Quadratic Residue
A number a that has a square root modulo p. There are (p-1)/2 quadratic residues mod p. Non-residues have no square roots.
Two Roots
If x is a square root, then p-x is also a root: x^2 = (p-x)^2 = a (mod p). Roots are negatives of each other mod p.
Euler Criterion
a^((p-1)/2) mod p = 1 means a is a quadratic residue. Result = p-1 (i.e., -1) means non-residue. Quick check.
Tonelli-Shanks
The standard algorithm for finding modular square roots when p is odd. Works for all p in polynomial time. Used in practice.
Teaching Example: Find sqrt(3) mod 11. Euler: 3^((11-1)/2)=3^5=243 mod 11 = 1. Sqrt exists! Trial: 1^2=1, 2^2=4, 3^2=9, 4^2=16=5, 5^2=25=3. Found! Root1=5. Root2=11-5=6. Verify: 5^2=25=3 mod 11, 6^2=36=3 mod 11. Both correct!
Free online calculators and tools covering mathematics, unit conversion, text processing, and daily life. Accurate, fast, mobile-friendly, and completely free to use.