A quadratic residue is an element that is congruent to a square in a finite field. For a prime modulus p, a is a residue when some x satisfies x² ≡ a mod p; otherwise it is a nonresidue. For polynomials modulo an irreducible polynomial f, A is a polynomial quadratic residue when another polynomial squares to A modulo f. The distinction is operational: only residues have the square roots needed to recover y-coordinates from elliptic-curve equations. section 2.4 section 12.0
Over a prime field, the Legendre symbol classifies a modulo p: 0 when p divides a, 1 for a residue, and −1 for a nonresidue. A result of 1 permits square-root computation; a nonresidue has no square root modulo p. GMP exposes this test through mpz_legendre, allowing a residue check before attempting the more expensive root routine. section 2.4 section 2.5
Prime-field check
Modulo 23, 2 is a quadratic residue because 5² mod 23 = 2, so (2/23) = 1. By contrast, (17/23) = −1, which means 17 has no square root modulo 23. section 2.4
After a residue test succeeds, select the square-root path from the field modulus:
- For p ≡ 3 mod 4, compute x = a^((p+1)/4) mod p. section 2.5
- For p ≡ 1 mod 4, decompose p − 1 = 2^e q with q odd, choose a quadratic nonresidue, and run Tonelli–Shanks until its loop variable reaches 1. section 2.5
- For extension fields represented by polynomials, use the corresponding p^k congruence test; use exponentiation when p^k ≡ 3 mod 4 and Tonelli–Shanks otherwise. section 12.1 section 12.4
A polynomial residue test reduces the question to a value in the coefficient prime field. Compute the resultant of A and the irreducible modulus f, then test whether resultant(A, f)^((p−1)/2) equals 1 modulo p. Equality means A is a quadratic residue and has a square root modulo f. Pseudo-division supports the resultant calculation. section 12.1 section 12.2.4
Figure 12.2 Polynomial quadratic residue algorithm to determine whether a polynomial has a square root
This flow diagram connects polynomial residue testing to the decision to compute, or reject, a polynomial square root. section 12.1
Residue testing also drives polynomial curve-point embedding. Evaluate the curve right-hand side at a candidate x, test it with poly_sqr, and increment x until the value is a residue. Its square root supplies one y-coordinate; negating that polynomial supplies the paired point. section 13.2.3
