The Legendre symbol tests whether an integer has a modular square root for an odd prime p. It returns 0 when p divides a, 1 when a is a quadratic residue modulo p, and −1 otherwise. section 2.4
Use the result to guide modular-square-root and curve-point computations:
- A result of 1 means that a square root exists; a result of −1 means that no modular square root exists. section 2.4
- In GMP, test a value with mpz_legendre(x, modulus), as shown by the compact msqr routine. section 2.4
- For elliptic-curve embedding, compute f(x), test its Legendre symbol, and increment x until the result is 1. section 3.1.5
Testing candidate curve coordinates
For the curve y² = x³ + 23x − 1 mod 43, x = 27 gives f(x) = 7, whose Legendre symbol is not 1. The same failure occurs at x = 28 and x = 29. At x = 30, the test equals 1, yielding y = 4 or −4. section 3.1.5
Listing 2.5 Legendre symbol
int msqr(mpz_t x)
{
return mpz_legendre(x, modulus); #1
}
A minimal GMP listing maps the mathematical test directly to mpz_legendre with a local modulus. section 2.4
