A square root of an element is a value whose square returns that element. In finite fields, not every value has one: a value that does is a quadratic residue. This distinction matters when solving an elliptic-curve equation of the form y² = f(x), because a valid y-coordinate exists only when f(x) has a square root. section 2.7 section 3.1.5
Over a prime field, square roots use a power computation when the prime is congruent to 3 mod 4; otherwise, use the Tonelli-Shanks algorithm. Before attempting either computation, test whether the input is a quadratic residue. This avoids searching for a root that does not exist. section 2.7 section 3.1.5
Embedding an x-value on a finite-field curve
For y² = x³ + 23x − 1 mod 43, start with x = 27. The right side is 7, whose Legendre-symbol test fails; x = 28 gives 20 and x = 29 also fails. At x = 30, the test succeeds and the two roots are y = 4 and y = −4. Increment x until f(x) is a quadratic residue, then take its square root to obtain a curve point. section 3.1.5
Figure 3.7 Embedding data on a curve
The flow shows the operational sequence: compute f(x), test it for a square root, increment x on failure, and derive y on success. section 3.1.5
The same task extends to fields defined by an irreducible polynomial, where coordinates are polynomials. To solve y² = f(x), determine first whether the polynomial is a quadratic residue. A polynomial A modulo prime polynomial f has a root when resultant(A, f)^((p−1)/2) = 1. The resultant is computed through pseudo-division and reduction. section 12.1 section 12.4
A practical polynomial-root routine proceeds in dependency order:
- Remove or obtain the polynomial content, the gcd of its coefficients. section 12.2 section 12.4
- Use pseudo-division and reduction to compute the resultant. section 12.2 section 12.4
- Raise the resultant to (p−1)/2 and compare the result with 1 to test quadratic residuosity. section 12.1 section 12.2.4
- Compute the root as A^((p^k+1)/4) when the extension field is congruent to 3 mod 4; otherwise use Tonelli-Shanks. section 12.4
Figure 12.1 Polynomial square root algorithm for finding \(y\) value of point on elliptic curve
The algorithm diagram connects the extension-field residue check and root computation to finding an elliptic-curve y-coordinate. section 12.1
This machinery supports random-point generation on field-extension elliptic curves, which is needed before pairing calculations. Although general polynomial factorization can be deep, the required path is narrower: test for a root, then compute it with the appropriate exponentiation or Tonelli-Shanks procedure. section 12.0 section 12.2
