Quadratic Residues — deciding if x² ≡ a (mod n) has a solution before you go looking for one

An integer a is a quadratic residue (QR) mod n if some x satisfies x² ≡ a (mod n); otherwise it's a non-residue (QNR). For an odd prime p, exactly (p-1)/2 of the nonzero residues mod p are QRs and (p-1)/2 are QNRs — an even split — and this existence question is the gate you check *before* spending effort on an actual square-root algorithm.

The signal that gives it away

- You need to know whether x² ≡ a (mod n) has *any* solution at all — not the value of x itself — before committing to a square-root routine. If the challenge only ever asks "does a root exist," running a full root-finding algorithm is wasted work. - The modulus is a prime or a prime power — that's exactly the case where the QR question has a cheap, direct answer (Euler's criterion). If instead the modulus is composite with unknown factorization, you're no longer in "cheap gate" territory — see below. - A protocol or oracle leaks a single residuosity bit for a value: this is the shape of Rabin decryption's 4-root ambiguity (the decryptor needs extra info, often phrased as a QR bit, to pick the right root among four), Goldwasser–Micali ciphertext bits, or a QR-based coin-flip/commitment scheme. - You're validating a candidate x-coordinate on a curve, or any place where the natural instinct is to brute-force "try roots until one squares to a" for a modulus large enough that brute force is not actually an option — that instinct is the anti-pattern; the residue question is the thing to answer first.

How it's exploited

1. For a known prime `p`, use Euler's criterion — this is the fast path and the main tool: ``python def is_qr(a, p): # p odd prime a %= p return a != 0 and pow(a, (p - 1) // 2, p) == 1 ` pow(a, (p-1)//2, p) lands on exactly one of three values: 1 means QR, p-1 means QNR, 0 means p | a (degenerate case, not really a residue question anymore). This is a single modular exponentiation — O(log p) — cheap even at cryptographic sizes, and it settles the question without ever touching a root-finding algorithm. 2. **For small n, you can just enumerate** — square every value 0..n-1 mod n and collect the results into the residue set. This is a legitimate, useful sanity-check / small-case tool, but it's an O(n) brute force: reach for Euler's criterion instead the moment n is cryptographically sized, not the enumeration. 3. **Once you've confirmed a QR exists and you actually need the root value**, hand off: - General odd prime p`: Tonelli-Shanks — computing an actual modular square root, not just whether one exists. - Special case p ≡ 3 (mod 4): a closed-form shortcut, x = a^((p+1)/4) mod p — no algorithm needed, just one more exponentiation. This shortcut is *only* valid for that specific congruence class of p; see the pitfall below. 4. For composite `n`, the residue question factors through the prime-power components — if you know (or can find) n's factorization, test/solve mod each prime-power factor independently, then recombine via Chinese Remainder Theorem — recombining residues across coprime moduli. This is also why *finding* a square root mod a large composite n is exactly as hard as factoring n — a proven equivalence: a square root gives you a factor of n (the same gcd trick used in Fault Injection Attacks — one faulty RSA-CRT signature factors the modulus outright-style CRT faults), and knowing the factorization is what lets you compute roots at all. Rabin's cryptosystem builds its security directly on that equivalence. Goldwasser–Micali is different: it relies on *deciding* QR-ness (not finding roots) being hard, and that's a separate problem — see the pitfall below.

What does NOT work

- Brute-force enumeration (squaring `0..n-1`) at cryptographic size. It's the right tool for a toy-sized n you're using to sanity-check your understanding, and the wrong tool the moment n has more than a handful of digits — that's exactly the regime Euler's criterion exists to replace. - Assuming the `p ≡ 3 (mod 4)` root shortcut generalizes to every prime. It only works for that one congruence class. For p ≡ 1 (mod 4) there is no equivalent one-line closed form — you need the general algorithm, Tonelli-Shanks — computing an actual modular square root, not just whether one exists. Applying the a^((p+1)/4) formula to a prime that doesn't satisfy p ≡ 3 (mod 4) silently produces a wrong value, not an error, so this is an easy trap to miss until an answer just doesn't check out. - Running Euler's criterion on a composite modulus and trusting the result as a residuosity answer. Euler's criterion is a prime-modulus tool; pow(a, (n-1)//2, n) on composite n doesn't have the same clean three-way meaning. The composite-modulus analogue with a public, factoring-free computation is the Jacobi Symbol — the factoring-free residuosity bit, and why +1 lies on a composite modulus — but it comes with its own sharp caveat (its +1 result is inconclusive, only -1 is a definite non-residue answer), so don't reach for it expecting a clean yes/no the way Euler's criterion gives you on a prime. - Expecting to "shortcut" residuosity on a composite modulus without factoring it. If the factorization of n is unknown, deciding QR-ness mod n is not a cheap gate anymore — it's the quadratic residuosity assumption (QRA), a standalone cryptographic hardness assumption that Goldwasser–Micali and QR-based commitment schemes rest on. Don't conflate it with the *root-finding* equivalence above: knowing n's factorization is *sufficient* to decide QR-ness cheaply (Legendre symbol on each prime factor), but no proof shows the converse — that an efficient QR-deciding oracle would let you factor n. So QRA is only known to be no harder than factoring; it isn't a proven equivalence the way root-finding is. There is no trick that skips straight to an answer here; if you genuinely need it, the real work is factoring n (see Integer Factorization Methodology — which factoring attack to try, in what order), not iterating on residue tests.

Related

Legendre Symbol — the O(log p) yes/no on square-root existence, before you touch Tonelli-Shanks 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 Chinese Remainder Theorem — recombining residues across coprime moduli Integer Factorization Methodology — which factoring attack to try, in what order Fault Injection Attacks — one faulty RSA-CRT signature factors the modulus outright