A quadratic nonresidue modulo a prime p is a value that is not congruent to x² for any x modulo p. It therefore has no square root in that field. The Legendre symbol classifies a as 0 when p divides a, 1 for a quadratic residue, and −1 for a nonresidue. section 2.4
Modulo 23
Because 5² mod 23 = 2, 2 is a quadratic residue and (2/23) = 1. In contrast, (17/23) = −1, so no value squared modulo 23 equals 17. section 2.4
Residue testing is the entry check for modular square-root code: reject a nonresidue before attempting a root. GMP exposes this test through mpz_legendre using the active modulus. section 2.4 section 2.5
For p congruent to 1 mod 4, Tonelli–Shanks writes p−1 = 2^e q with q odd, then selects a random quadratic nonresidue n. About half the values modulo p are nonresidues on average, making this selection quick. The chosen n initializes the powers that drive the loop toward b = 1. section 2.5
Figure 2.3 Compute square root mod p
Follow the square-root decision flow: test for a residue first, use direct exponentiation for the easy modulus case, and otherwise enter Tonelli–Shanks. section 2.5
The same role extends to polynomials modulo an irreducible prime polynomial. To decide whether polynomial a has a square root, compute res(f,a)^((p−1)/2) and test whether it equals 1; otherwise a is not a quadratic residue. This supports finding the y coordinate on an elliptic curve. section 12.1
