Legendre Symbol — the O(log p) yes/no on square-root existence, before you touch Tonelli-Shanks

The Legendre symbol (a/p) for an odd prime p is +1 if a is a quadratic residue mod p, -1 if it's a non-residue, and 0 if p | a — it answers "does x² ≡ a (mod p) have a solution" in O(log p) without ever finding the root.

The signal that gives it away

- You need to know whether x² ≡ a (mod p) is solvable at all, and the modulus is a known prime (not composite, not unfactored) — that's Legendre's exact job, and it's the gate you check *before* spending effort on an actual square-root algorithm like Tonelli-Shanks — computing an actual modular square root, not just whether one exists. - A protocol or oracle leaks a single bit that turns out to be "is this value a QR mod p" — residuosity-as-oracle shows up in Rabin-style decryption ambiguity resolution and Goldwasser-Micali-flavored bit-leak challenges. Recognize it: the challenge hands you a value and a yes/no, and that yes/no is literally the sign of the Legendre symbol. - Elliptic-curve setup code that, given an x coordinate, checks x³ + a·x + b is a QR mod p before accepting the point — that check is a Legendre-symbol computation in disguise, and it's how you validate whether a given x even has a y on the curve before calling Tonelli-Shanks to find it. - Any place you'd otherwise be tempted to brute-force "try all y until y² == a mod p" for a large prime p — that's the anti-pattern; Legendre tells you in one modular exponentiation whether that search can even succeed.

How to exploit it

1. Compute it via Euler's criterion: (a/p) ≡ a^((p-1)/2) (mod p), with the result mapped into {-1, 0, 1} (the raw modular exponentiation lands on 0, 1, or p-1; map p-1 → -1). This is one pow(a, (p-1)//2, p) call — cheap even for cryptographically-sized primes, because modular exponentiation is O(log p) modular multiplications, no factorization involved. ``python def legendre(a, p): a %= p if a == 0: return 0 return 1 if pow(a, (p - 1) // 2, p) == 1 else -1 ` In SageMath: legendre_symbol(a, p). 2. Use **complete multiplicativity** — (ab/p) = (a/p)(b/p) — to simplify before reducing. Two residues or two non-residues multiply to a residue; a residue times a non-residue is a non-residue. This lets you decide the residuosity of a product or a large composite expression from its factors' symbols instead of reducing the whole product mod p first, which matters when you're triaging many candidate values fast (e.g. scanning x coordinates for curve point validity). 3. Once you know a root exists ((a/p) = +1`), reach for Tonelli-Shanks — computing an actual modular square root, not just whether one exists to actually *compute* the square root — Legendre only answers existence, never the value. Running Tonelli-Shanks on a non-residue is a wasted call at best and a wrong answer at worst; always gate it with Legendre first. 4. As a building block toward composite moduli: the Legendre symbol only makes sense for a prime p. If your modulus is composite (or its factorization is exactly what you're trying to hide/find), the right generalization is the Jacobi Symbol — the factoring-free residuosity bit, and why +1 lies on a composite modulus — same O(log n) computation via the same exponentiation-and-multiplicativity idea, but read the caveat below before trusting its output as a residuosity test.

What does NOT work

- Using the Jacobi symbol as a drop-in QR test on a composite modulus. The Jacobi symbol (a/n) for composite odd n is multiplicative and computed the same cheap way, but (a/n) = +1 does not imply a is actually a quadratic residue mod n — it can be +1 for a genuine non-residue when n's factors each contribute -1 and the signs cancel. Only (a/n) = -1 is a definite, actionable statement ("a is provably not a QR mod at least one prime factor"). Don't reuse Legendre-style "+1 means solvable" logic on a composite modulus — that's exactly the bug this distinction exists to prevent. See Jacobi Symbol — the factoring-free residuosity bit, and why +1 lies on a composite modulus for the full asymmetry. - Brute-forcing square roots mod a large prime instead of computing the symbol first. For cryptographic-sized p, trying candidate y values until y² ≡ a is hopeless; the whole point of Legendre + Tonelli-Shanks is that both steps are polynomial-time via exponentiation, never search. - Skipping the existence check and running Tonelli-Shanks directly. It's tempting to jump straight to the square-root algorithm, but if (a/p) = -1 there is no root and the algorithm's assumptions are violated — check with Legendre first, it's orders of magnitude cheaper than debugging a square-root routine that's chasing a nonexistent answer.

Related

Quadratic Residues — deciding if x² ≡ a (mod n) has a solution before you go looking for one Jacobi Symbol — the factoring-free residuosity bit, and why +1 lies on a composite modulus Tonelli-Shanks — computing an actual modular square root, not just whether one exists Elliptic Curve Discrete Logarithm Problem — the curve order's factorization picks your attack