Quadratic residuosity problem

The quadratic residuosity problem 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 quadratic residuosity problem 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. 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 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: This is a multiplicative character which means ( a p ) = 1 {displaystyle {ig (}{ frac {a}{p}}{ig )}=1} for exactly ( p − 1 ) / 2 {displaystyle (p-1)/2} of the values 1 , … , p − 1 {displaystyle 1,ldots ,p-1} , and it is − 1 {displaystyle -1} for the remaining. It is easy to compute using the law of quadratic reciprocity in a manner akin to the Euclidean algorithm, see Legendre symbol. Consider now some given N = p 1 p 2 {displaystyle N=p_{1}p_{2}} where p 1 {displaystyle p_{1}} and p 2 {displaystyle p_{2}} are two, different unknown primes.A given a {displaystyle a} is a quadratic residue modulo N {displaystyle N} if and only if a {displaystyle a} is a quadratic residue modulo both p 1 {displaystyle p_{1}} and p 2 {displaystyle p_{2}} . Since we don't know p 1 {displaystyle p_{1}} or p 2 {displaystyle p_{2}} , we cannot compute ( a p 1 ) {displaystyle {ig (}{ frac {a}{p_{1}}}{ig )}} and ( a p 2 ) {displaystyle {ig (}{ frac {a}{p_{2}}}{ig )}} . However, it is easy to compute their product.This is known as the Jacobi symbol: