A modular square root of a is an x satisfying x² ≡ a mod p, where p is prime. This operation recovers an elliptic-curve y-coordinate from y² = x³ + a₄x + a₆, so it matters in finite-field cryptography. Unlike ordinary real square roots, a solution may not exist. section 2.0 section 2.4
Use this implementation flow:
- Test whether a is a quadratic residue. The Legendre symbol returns 1 for a nonzero residue, −1 for a nonresidue, and 0 when p divides a; a nonresidue has no modular square root. section 2.4
- If p ≡ 3 mod 4, compute x = a^((p+1)/4) mod p using modular exponentiation. section 2.5
- If p ≡ 1 mod 4, write p − 1 = 2ᵉq with q odd, choose a quadratic nonresidue n, initialize the Tonelli–Shanks state, and iterate until the correction state reaches 1. section 2.5
Small finite-field checks
For a = 2 and p = 23, x = 5 works because 5² mod 23 = 2, and the Legendre symbol is 1. For a = 17 and p = 23, the symbol is −1, so no square root exists. section 2.4
Figure 2.3 Compute square root mod p
Use the process diagram to connect residue testing, modulus classification, and the two computation branches. section 2.5
