Quadratic Residuosity Problem

The quadratic residuosity problem (QRP) is the computational problem of determining whether a given integer \(a\) is a quadratic residue modulo a composite number \(n = pq\) whose prime factorization is unknown. Unlike the case for prime moduli — where Euler's criterion provides an efficient test — no polynomial-time algorithm is known for the composite case, and the problem is believed to be as hard as integer factorization itself. This hardness assumption underpins the security of the Blum-Blum-Shub pseudorandom generator and several public-key cryptosystems.

The quadratic residuosity problem is a decision problem in the complexity class NP that is not known to be NP-complete, placing it among the candidate problems for cryptographic hardness that may survive even if P = NP. Its special status — hard on average but not necessarily worst-case — makes it a paradigmatic example of a problem whose computational difficulty is structural rather than combinatorial.