Residuosity

Residuosity is a term used in number theory to describe the study of residues modulo a positive integer n and, in particular, the question of whether a given integer a is a residue with respect to n. A residue modulo n is a representative of a congruence class modulo n, typically taken in the set {0,1,…,n−1}. When a residue has a special form, such as being a square, it is called a quadratic residue. More generally, residuosity concerns the decidability and structure of residue classes under various arithmetic operations.

Quadratic residues and prime moduli: An integer a is a quadratic residue modulo p (a prime) if there exists x with x^2 ≡ a mod p. For a nonzero a mod p, exactly (p−1)/2 of the p−1 residues are nonzero quadratic residues. The Legendre symbol (a/p) encodes residuosity: (a/p)=1 if a is a quadratic residue mod p, (a/p)=−1 if not, and 0 if a ≡ 0 mod p. Euler's criterion states that a^((p−1)/2) ≡ (a/p) (mod p).

Composite moduli and computational residuosity: For composite n, determining whether a is a quadratic residue modulo n is more difficult. In particular, when n is a product of two large primes (n=pq), the quadratic residuosity problem asks for an efficient procedure to decide residuosity without factoring n. This hardness underpins several cryptographic schemes. In practice, the Jacobi symbol (a|n) can be computed quickly and may equal −1 or 1, but it can be inconclusive for composite n: (a|n)=1 does not guarantee that a is a residue modulo n.

Applications and related concepts: The notion of residuosity is central to cryptosystems such as Goldwasser–Micali and Rabin, which rely on the difficulty of distinguishing residues from non-residues. Related ideas include quadratic residues modulo primes, the Jacobi and Legendre symbols, and Blum integers (n with p and q ≡ 3 mod 4).