Jacobi Symbol — the factoring-free residuosity bit, and why +1 lies on a composite modulus

The Jacobi symbol (a/n) generalizes the Legendre symbol to any odd n = ∏ pᵢ^eᵢ — composite or prime, factored or not — as the product ∏ (a/pᵢ)^eᵢ, computable in O(log a · log n) via the same reciprocity recurrence as the Euclidean algorithm, without ever factoring n.

The signal that gives it away

- The modulus is odd but either composite or of unknown/unstated factorization, and the challenge (or your own triage) wants a fast residuosity-style bit before committing to heavier machinery — this is the exact situation where Legendre doesn't apply directly (it needs a known prime) but Jacobi does. - You're implementing or recognizing Solovay–Strassen primality testing: for a candidate n and random base a, the test compares (a/n) (Jacobi, cheap) against a^{(n-1)/2} mod n (Euler's criterion, also cheap); disagreement between the two proves n composite outright, agreement across many bases is evidence (not proof) of primality. If challenge source computes both quantities and compares them, that's Solovay–Strassen, not Miller–Rabin. - A challenge exposes a Jacobi-symbol-as-predicate / one-way bit: quadratic-residuosity-flavored commitments, a Goldwasser–Micali-style encryption scheme, or any oracle that hands back ±1 for values it guarantees all have Jacobi symbol +1. The tell is specifically that guarantee — restricting inputs to (a/n) = +1 is what turns "is a a QR mod n" from a cheap, publicly-computable bit into a hard problem (the quadratic residuosity assumption), because within that +1 set genuine residues and genuine non-residues are indistinguishable without factoring n. - You're asked to reason about why a challenge's "is-QR" check on a composite modulus is unreliable — i.e., you're debugging or attacking someone else's flawed use of the Jacobi symbol as if it were a full residuosity test.

How it's exploited

1. Compute (a/n) via the reciprocity recurrence — factor out powers of 2 from a (each contributing a sign flip governed by n mod 8), swap arguments with the quadratic-reciprocity sign rule (a mod 4 == 3 and n mod 4 == 3 flips the sign), and reduce a mod n at each step, exactly like a sign-tracking Euclidean algorithm: ``python def jacobi(a, n): # n odd > 0 a %= n; r = 1 while a: while a % 2 == 0: a //= 2 if n % 8 in (3, 5): r = -r a, n = n, a if a % 4 == 3 and n % 4 == 3: r = -r a %= n return r if n == 1 else 0 ` 2. **Interpret the result correctly — this is the entire point of the technique:** - (a/n) = -1 ⇒ a is *definitely* a quadratic non-residue mod n (mod at least one prime factor, hence mod n). Actionable immediately, no factoring needed. - (a/n) = +1 ⇒ **inconclusive** for composite n. It means a is a residue mod *every* prime factor, OR a non-residue mod an *even* number of them — the signs cancel and you cannot tell which case you're in from the symbol alone. - (a/n) = 0 ⇒ gcd(a, n) > 1, i.e. you just found a factor of n for free (gcd(a, n)`) — don't discard this case, route straight to Integer Factorization Methodology — which factoring attack to try, in what order. 3. If you actually need true QR-ness mod a composite n (not just the symbol), there is no shortcut around factoring: recover the factorization (Integer Factorization Methodology — which factoring attack to try, in what order), apply Legendre Symbol — the O(log p) yes/no on square-root existence, before you touch Tonelli-Shanks independently mod each prime factor, then recombine the per-factor bits via Chinese Remainder Theorem — recombining residues across coprime moduli if you need the value itself, not just a yes/no. 4. For Solovay–Strassen as a primality test in either direction (implementing it, or recognizing it in challenge source to find its weak spot): run several random bases a; any base where jacobi(a, n) mod n != pow(a, (n-1)//2, n) proves n composite on the spot. If you're attacking a Solovay–Strassen-gated system, remember its error bound is 2^-k for k rounds — weaker per-round than Miller–Rabin's 4^-k — so a system trusting few rounds of Solovay–Strassen is a softer target for a planted pseudoprime than one using Miller–Rabin; see Primality Testing — confirming a number is prime without factoring it for the base case and Carmichael Numbers & λ(n) — the true group exponent, and why a lone Fermat test lies-style composite constructions. 5. When a challenge exposes a residuosity oracle restricted to +1-Jacobi inputs (Goldwasser–Micali flavor), recognize that the Jacobi symbol computation is *not* the attack surface — it's public, cheap, and by design gives no information within that restricted set. Redirect effort at factoring n (the actual quadratic residuosity assumption you're up against) rather than iterating on Jacobi-symbol tricks; see Integer Factorization Methodology — which factoring attack to try, in what order.

What does NOT work

- Treating `(a/n) = +1` as proof `a` is a quadratic residue mod composite `n`. This is the single most consequential mistake with this tool — it is *not* a weaker version of the Legendre test, it is a genuinely different, ambiguous statement whenever n is composite. Code that does if jacobi(a, n) == 1: # a is a QR is silently wrong on composite moduli and will misclassify non-residues with an even number of -1 factors. - Reaching for Jacobi when the modulus is a known prime. It still works (it degenerates to the Legendre symbol), but there's no reason to reach for the composite-generalized tool when Legendre Symbol — the O(log p) yes/no on square-root existence, before you touch Tonelli-Shanks's +1/-1 result is *always* conclusive — using Jacobi terminology/framing on a prime modulus just obscures that you actually have a definite answer, not an inconclusive one. - Expecting the Jacobi symbol to break a Goldwasser–Micali-style scheme. Computing (a/n) is cheap and public precisely because the scheme is built to guarantee it's always +1 for both encrypted-0 and encrypted-1 ciphertexts — the symbol carries zero information there by construction. If a challenge's "security" seems to hinge on hiding the Jacobi symbol itself, that's a fake or broken construction, not the real assumption; the real hardness is factoring n (or equivalently, distinguishing residues from non-residues within the +1 set), and no amount of clever Jacobi-symbol manipulation substitutes for that. - Skipping the `(a/n) = 0` case. It's easy to write interpretation logic that only branches on +1/-1 and silently mishandles 0. A 0 is a strictly better result than either — it hands you a nontrivial factor of n directly via gcd(a, n) — so dropping it wastes a free factoring win.

Related

Legendre Symbol — the O(log p) yes/no on square-root existence, before you touch Tonelli-Shanks Quadratic Residues — deciding if x² ≡ a (mod n) has a solution before you go looking for one Primality Testing — confirming a number is prime without factoring it Integer Factorization Methodology — which factoring attack to try, in what order Chinese Remainder Theorem — recombining residues across coprime moduli Carmichael Numbers & λ(n) — the true group exponent, and why a lone Fermat test lies