Engineering / Mathematics — Quadratic Residues
Testing Quadratic Residuosity: Prime Modulus
Deciding quadratic residuosity modulo a prime, and why the problem is easy in this case.
Executive summary
Modulo a prime, quadratic residuosity is decided in polynomial time by Euler's criterion or, faster, by the Legendre symbol algorithm.
The problem is easy precisely because the modulus has no hidden structure, which is what changes when the modulus is composite.
Learning objectives
- State the decision procedure for a prime modulus.
- Compare the available methods.
- Explain why primality makes the problem tractable.
01The decision procedure
Two methods decide the question, and both are polynomial time.
Decide residuosity mod a prime
prime p, integer aresidue or non-residue- Given odd prime p and integer a with p not dividing a.
- Compute the Legendre symbol (a|p) by the Euclid-style algorithm.
- Return residue if the symbol is 1, non-residue if −1.
O(len(p)²) bit operationsThe alternative, Euler's criterion, computes a^{(p−1)/2} mod p and reads off the result. It is a cubic-time method giving the same answer, and it is preferred only where fixed control flow matters.
02Why primality makes it easy
Modulo a prime, the units form a cyclic group and the residues are exactly the even powers of a generator — a subgroup of index 2. The quotient by that subgroup is the two-element group, and the quotient map is the Legendre symbol, which is efficiently computable.
Prime modulus
One subgroup of index 2, and the quotient map is computable. Residuosity is decided directly.
Composite modulus
Several subgroups of index 2. The Jacobi symbol computes one quotient; the residues are a strictly smaller set, and identifying them requires the factorisation.
03Consequences
| Task | Prime modulus | Composite modulus |
|---|---|---|
| Decide residuosity | Polynomial time | Believed hard without the factorisation |
| Compute a square root | Polynomial time (randomised) | Equivalent to factoring |
| Count square roots | Exactly 2 | 4 for pq; 2^k in general |
Every row changes in the same direction, and the reason is the same in each case: the composite modulus hides a decomposition that the prime modulus does not have. Knowing the decomposition restores all three to the easy column.
This is the structural fact that Goldwasser–Micali encryption and several related constructions are built on.
04Frequently asked questions
Is there any advantage to Euler's criterion here?
Constant-time behaviour. The Legendre algorithm branches on the operand values, so where the argument is secret the fixed exponentiation ladder is preferable despite being slower.
Does deciding residuosity give the square root?
No. The Legendre symbol answers yes or no without producing a witness. Extracting the root is a separate computation, and for p ≡ 1 (mod 4) it requires a randomised algorithm.
What about prime power moduli?
Residuosity modulo p^e for odd p reduces to residuosity modulo p, because the unit group is cyclic in both cases. The root is then lifted by Hensel's method.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 291.
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.