Engineering / Mathematics — Quadratic Residues
The Jacobi Symbol
The Jacobi symbol as the multiplicative extension of the Legendre symbol to odd composite moduli, and what it does and does not tell you.
Executive summary
The Jacobi symbol extends the Legendre symbol to odd composite moduli by multiplying the Legendre symbols of the prime factors. It inherits multiplicativity and reciprocity.
What it loses is the connection to residuosity: a Jacobi symbol of plus one does not mean the argument is a square, and that failure is exploited cryptographically.
Learning objectives
- Define the Jacobi symbol and state its properties.
- Identify precisely what it fails to determine.
- Explain its cryptographic significance.
01Definition
Jacobi symbol
For odd n = p₁^{e₁} ··· pₖ^{eₖ} and integer a,
(a|n) = ∏ᵢ (a|pᵢ)^{eᵢ}, a product of Legendre symbols.
The definition uses the factorisation, but the value is computable without it — this is the central point. Reciprocity and the supplementary laws hold for the Jacobi symbol verbatim, so the Euclid-style algorithm applies directly to composite moduli.
| Property | Holds for Jacobi? |
|---|---|
| Multiplicative in the numerator | Yes |
| Multiplicative in the denominator | Yes |
| Reciprocity | Yes |
| Supplementary laws | Yes |
| (a|n) = 1 implies a is a residue | No |
| (a|n) = −1 implies a is a non-residue | Yes |
02The one-sided implication
The smallest illustration: modulo 15 = 3 · 5, take a = 2. Then (2|3) = −1 and (2|5) = −1, so (2|15) = 1. Yet 2 is not a square modulo 15, since it is a square modulo neither factor.
(2|15) = (2|3)(2|5) = (−1)(−1) = +1, but 2 is not a QR mod 15For n = pq the units with Jacobi symbol +1 split evenly into genuine residues and pseudo-residues of this kind. Distinguishing the two halves is the quadratic residuosity problem.
03Cryptographic significance
The gap between computable Jacobi symbol and uncomputable residuosity is unusual and directly useful.
Public and private
Anyone can compute the Jacobi symbol from n alone. Only someone knowing the factorisation can decide residuosity.
A hard-core predicate
Residuosity within the Jacobi-plus-one set is believed hard, giving a bit that is hidden from an adversary but known to the key holder.
Encryption schemes
Goldwasser–Micali encrypts a bit as a random residue or pseudo-residue, with decryption requiring the factorisation.
04Frequently asked questions
Is the Jacobi symbol defined for even moduli?
Not in the standard definition, which requires n odd. The Kronecker symbol extends it further to include even moduli and negative arguments, at the cost of extra case handling.
Why is the Jacobi symbol computable without factoring?
Because reciprocity permits swapping numerator and denominator, and reduction shrinks both. The algorithm never needs to know the factorisation — it only needs the arguments to be odd, which extracting powers of two ensures.
How is a random element with Jacobi symbol +1 generated?
By drawing uniformly and computing the symbol, retrying on −1. Half of all units qualify, so the expected cost is two draws.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 287-289.
This page carries the durable method layer only: definitions, constructions, algorithms, complexity results and selection criteria, authored originally for KEVOS. No text is transcribed or paraphrased from the source, and no numeric tables or benchmark data are reproduced — these are routed to live authoritative sources instead.
Author: Kevin Jogin. Last reviewed 2026-08-07.