View source for 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|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|integer factorization]] itself. This hardness assumption underpins the security of the [[Blum-Blum-Shub]] pseudorandom generator and several [[Public-key cryptography|public-key cryptosystems]].

The quadratic residuosity problem is a decision problem in the complexity class [[Complexity theory|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.

[[Category:Mathematics]]
[[Category:Cryptography]]
[[Category:Computer Science]]