Engineering / Mathematics — Quadratic Residues
Testing Quadratic Residuosity: Prime Power and Composite Modulus
Quadratic residuosity modulo prime powers and composites, the reduction by Chinese remaindering, and where the hardness enters.
Executive summary
Residuosity modulo a composite reduces by the Chinese remainder theorem to residuosity modulo each prime power factor. Given the factorisation this is easy.
Without the factorisation the problem is believed hard, and the Jacobi symbol supplies only a partial answer.
Learning objectives
- Reduce composite residuosity to prime power residuosity.
- Handle prime power moduli including powers of two.
- Locate exactly where the hardness enters.
01Prime power moduli
Residuosity modulo an odd prime power
For odd prime p and a coprime to p, a is a quadratic residue modulo p^e if and only if it is a quadratic residue modulo p.
The unit group modulo p^e is cyclic, so the same index-2 argument applies, and residuosity is detected at the base prime. A root modulo p lifts to a root modulo p^e by Hensel's method.
| Modulus | Residuosity condition for odd a |
|---|---|
| 2 | Always |
| 4 | a ≡ 1 (mod 4) |
| 2^e, e ≥ 3 | a ≡ 1 (mod 8) |
| p^e, p odd | a is a QR mod p |
02Composite moduli given the factorisation
Residuosity mod a composite, factorisation known
a, n with the factorisation of nresidue or non-residue mod n- Factor n into prime powers.
- For each odd prime power p^e, test whether a is a residue mod p by Legendre symbol.
- For the power of two, apply the congruence condition from the table.
- Return residue only if every component test succeeds.
O(k · len(n)²) for k prime power factorsThe correctness is the Chinese remainder theorem: an element is a square in a product ring exactly when each component is a square.
03Where the hardness enters
Quadratic residuosity problem
Given n = pq and a with (a|n) = 1, decide whether a is a quadratic residue modulo n.
- With the factorisation
O(len(n)²)Two Legendre symbol computations - Without, using Jacobi
O(len(n)²)Detects non-residues only when the symbol is −1 - Without, general case
No efficient method knownThe quadratic residuosity assumption
For n = pq, the units with Jacobi symbol +1 divide evenly: half are genuine residues, half are pseudo-residues with both Legendre symbols equal to −1. Telling them apart is exactly the hard problem, and it is what Goldwasser–Micali encryption relies on.
04Frequently asked questions
Why is the condition modulo 8 rather than 4 for large powers of two?
Because Z_{2^e}* for e ≥ 3 is a product of a group of order 2 and a cyclic group, so the squares form a subgroup of index 4 rather than 2. The condition a ≡ 1 (mod 8) is exactly membership in that subgroup.
Is the quadratic residuosity problem as hard as factoring?
It is no harder — the factorisation solves it. Whether it is as hard is unknown, so it is a separate assumption, formally weaker than the factoring assumption.
Does a Jacobi symbol of −1 settle the question?
Yes, conclusively: an element with Jacobi symbol −1 cannot be a square, since a square has all constituent Legendre symbols equal to 1. Only the +1 case is ambiguous.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 291-292.
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.