The quadratic residuosity problem (QRP) in computational number theory is to decide, given integers a {\displaystyle a} and N {\displaystyle N} , whether a {\displaystyle a} is a quadratic residue modulo N {\displaystyle N} or not. Here N = p 1 p 2 {\displaystyle N=p_{1}p_{2}} for two unknown primes p 1 {\displaystyle p_{1}} and p 2 {\displaystyle p_{2}} , and a {\displaystyle a} is among the numbers which are not obviously quadratic non-residues (see below). The problem was first described by Gauss in his Disquisitiones Arithmeticae in 1801. This problem is believed to be computationally difficult. Several cryptographic methods rely on its hardness, see § Applications. An efficient algorithm for the quadratic residuosity problem immediately implies efficient algorithms for other number theoretic problems, such as deciding whether a composite N {\displaystyle N} of unknown factorization is the product of 2 or 3 primes.
Precise formulation Given integers a {\displaystyle a} and T {\displaystyle T} , a {\displaystyle a} is said to be a quadratic residue modulo T {\displaystyle T} if there exists an integer b {\displaystyle b} such that
a ≡ b 2 ( mod T ) {\displaystyle a\equiv b^{2}{\pmod {T}}} . Otherwise we say it is a quadratic non-residue. When T = p {\displaystyle T=p} is a prime, it is customary to use the Legendre symbol:
( a p ) = { 1 if a is a quadratic residue modulo p and a ≢ 0 ( mod p ) , − 1 if a is a quadratic non-residue modulo p , 0 if a ≡ 0 ( mod p ) . {\displaystyle \left({\frac {a}{p}}\right)={\begin{cases}1&{\text{ if }}a{\text{ is a quadratic residue modulo }}p{\text{ and }}a\not \equiv 0{\pmod {p}},\\-1&{\text{ if }}a{\text{ is a quadratic non-residue modulo }}p,\\0&{\text{ if }}a\equiv 0{\pmod {p}}.\end{cases}}}
… excerpt ends here. Continue reading the full article.
