Engineering / Mathematics — Quadratic Residues
Computing Modular Square Roots: Composite Modulus
Square roots modulo a composite, the four roots for a semiprime, and the equivalence with factoring.
Executive summary
Given the factorisation, square roots modulo a composite are assembled from roots modulo each prime power by Chinese remaindering.
Without the factorisation the problem is exactly as hard as factoring, because two independent square roots of the same value split the modulus.
Learning objectives
- Assemble a composite square root from prime power roots.
- Count the roots for a general modulus.
- Prove the equivalence with factoring.
01Assembly given the factorisation
Square root mod a composite
a, n with the factorisation of nall square roots of a modulo n- Factor n into prime powers pᵢ^{eᵢ}.
- For each factor, compute a square root xᵢ of a modulo pᵢ^{eᵢ}.
- If any factor admits no root, report that a is not a residue mod n.
- Chinese remainder the xᵢ to obtain a root modulo n.
- Varying the sign of each xᵢ independently yields all roots.
O(k · len(n)²) plus the reconstructionFor n = pq with distinct odd primes, the two sign choices give four combinations and hence four square roots. In general the count is 2^k for k distinct odd prime factors, adjusted for the power of two.
02Equivalence with factoring
Square roots yield the factorisation
For n = pq, an algorithm producing a square root of an arbitrary residue modulo n yields the factorisation in expected polynomial time.
Reason. Choose x at random, set a = x² mod n, and ask the algorithm for a root y. With probability 1/2 the returned root satisfies y ≢ ±x, and then gcd(x − y, n) is a proper factor.
The converse is the assembly procedure above. So the two problems are equivalent, and square root extraction modulo a composite is a hard problem exactly to the extent that factoring is.
03Consequences for protocol design
Rabin cryptosystem
Encryption is squaring; decryption requires the factorisation. Security provably equivalent to factoring, at the cost of ambiguous decryption.
Blum integers
Moduli n = pq with both primes congruent to 3 mod 4. Every residue then has exactly one square root that is itself a residue, giving a canonical choice.
Fiat-Shamir identification
Proves knowledge of a square root without revealing it, relying on the same hardness.
Blum integers are the standard convenience. With both primes congruent to 3 modulo 4, each prime-modulus root is a single exponentiation and the four composite roots include exactly one that is a residue, which resolves the ambiguity canonically.
04Frequently asked questions
Why exactly four roots for a semiprime?
Because each of the two prime factors admits two roots, and the Chinese remainder theorem makes the choices independent. Four combinations give four distinct roots modulo n.
Is Rabin encryption used in practice?
Rarely, despite its stronger security proof. The ambiguous decryption requires added redundancy, and the chosen-ciphertext vulnerability needs careful padding — enough friction that RSA prevailed.
What makes a Blum integer convenient?
Both prime factors are 3 mod 4, so each prime-modulus square root is a single exponentiation, and the squaring map restricted to residues is a permutation with a canonical inverse.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 296-297.
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.