Editing Quadratic residuosity problem

{{Short description|Problem in computational number theory}}
The '''quadratic residuosity problem''' ('''QRP'''<ref>{{cite book|last1=Kaliski|first1=Burt|title=Encyclopedia of Cryptography and Security |chapter=Quadratic Residuosity Problem |year=2011|page=1003|doi=10.1007/978-1-4419-5906-5_429|isbn=978-1-4419-5905-8 |doi-access=free}}</ref>) in [[computational number theory]] is to decide, given [[integer]]s <math>a</math> and <math>N</math>, whether <math>a</math> is a [[quadratic residue]] [[modular arithmetic|modulo]] <math>N</math> or not.
Here <math>N = p_1 p_2</math> for two unknown [[prime number|primes]] <math>p_1</math> and <math>p_2</math>, and <math>a</math> 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 [[Computational complexity theory|computationally difficult]].
Several cryptographic methods [[Computational hardness assumption|rely on its hardness]], see {{section link||Applications}}.

An efficient [[algorithm]] for the quadratic residuosity problem immediately implies efficient algorithms for other [[number theoretic]] problems, such as deciding whether a [[composite number|composite]] <math>N</math> of unknown factorization is the product of 2 or 3 primes.<ref>{{cite conference |author=Adleman, L. |title=On Distinguishing Prime Numbers from Composite Numbers | book-title=Proceedings of the 21st IEEE Symposium on the Foundations of Computer Science (FOCS), Syracuse, N.Y. |year=1980 |pages=387–408 |doi=10.1109/SFCS.1980.28 |issn=0272-5428}}</ref>

== Precise formulation ==

Given integers <math>a</math> and <math>T</math>, <math>a</math> is said to be a ''quadratic residue modulo <math>T</math>'' if there exists an integer <math>b</math> such that
:<math>a \equiv b^2 \pmod T</math>.
Otherwise we say it is a quadratic non-residue.
When <math>T = p</math> is a prime, it is customary to use the [[Legendre symbol]]:
:<math>\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}</math>

This is a [[character (mathematics)|multiplicative character]] which means <math>\big(\tfrac{a}{p}\big) = 1</math> for exactly <math>(p-1)/2</math> of the values <math>1,\ldots,p-1</math>, and it is <math>-1</math> 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 <math>N = p_1 p_2</math> where <math>p_1</math> and <math>p_2</math> are two different unknown primes.
A given <math>a</math> is a quadratic residue modulo <math>N</math> [[if and only if]] <math>a</math> is a quadratic residue modulo both <math>p_1</math> and <math>p_2</math> and <math>\gcd(a, N) = 1</math>.

Since we don't know <math>p_1</math> or <math>p_2</math>, we cannot compute <math>\big(\tfrac{a}{p_1}\big)</math> and <math>\big(\tfrac{a}{p_2}\big)</math>. However, it is easy to compute their product.
This is known as the [[Jacobi symbol]]:
:<math>\left(\frac{a}{N}\right) = \left(\frac{a}{p_1}\right)\left(\frac{a}{p_2}\right)</math>

This also [[Jacobi symbol#Calculating the Jacobi symbol|can be efficiently computed]] using the [[law of quadratic reciprocity]] for Jacobi symbols.

However, <math>\big(\tfrac{a}{N}\big)</math> cannot in all cases tell us whether <math>a</math> is a quadratic residue modulo <math>N</math> or not!
More precisely, if <math>\big(\tfrac{a}{N}\big) = -1</math> then <math>a</math> is necessarily a quadratic non-residue modulo either <math>p_1</math> or <math>p_2</math>, in which case we are done.
But if <math>\big(\tfrac{a}{N}\big) = 1</math> then it is either the case that <math>a</math> is a quadratic residue modulo both <math>p_1</math> and <math>p_2</math>, or a quadratic non-residue modulo both <math>p_1</math> and <math>p_2</math>.
We cannot distinguish these cases from knowing just that <math>\big(\tfrac{a}{N}\big) = 1</math>.

This leads to the precise formulation of the quadratic residue problem:

'''Problem:'''
Given integers <math>a</math> and <math>N = p_1 p_2</math>, where <math>p_1</math> and <math>p_2</math> are distinct unknown primes, and where <math>\big(\tfrac{a}{N}\big) = 1</math>, determine whether <math>a</math> is a quadratic residue modulo <math>N</math> or not.

== Distribution of residues ==

If <math>a</math> is drawn [[discrete uniform distribution|uniformly at random]] from integers <math>0,\ldots,N-1</math> such that <math>\big(\tfrac{a}{N}\big) = 1</math>, is <math>a</math> more often a quadratic residue or a quadratic non-residue modulo <math>N</math>?

As mentioned earlier, for exactly half of the choices of <math>a \in \{1,\ldots,p_1-1\}</math>, then <math>\big(\tfrac{a}{p_1}\big) = 1</math>, and for the rest we have <math>\big(\tfrac{a}{p_1}\big) = -1</math>.
By extension, this also holds for half the choices of <math>a \in \{1,\ldots,N-1\} \setminus p_1\mathbb{Z}</math>.
Similarly for <math>p_2</math>.
From basic algebra, it follows that this partitions <math>(\mathbb{Z}/N\mathbb{Z})^{\times}</math> into 4 parts of equal size, depending on the sign of <math>\big(\tfrac{a}{p_1}\big)</math> and <math>\big(\tfrac{a}{p_2}\big)</math>.

The allowed <math>a</math> in the quadratic residue problem given as above constitute exactly those two parts corresponding to the cases <math>\big(\tfrac{a}{p_1}\big) = \big(\tfrac{a}{p_2}\big) = 1</math> and <math>\big(\tfrac{a}{p_1}\big) = \big(\tfrac{a}{p_2}\big) = -1</math>.
Consequently, exactly half of the possible <math>a</math> are quadratic residues and the remaining are not.

==Applications==

The intractability of the quadratic residuosity problem is the basis for the security of the [[Blum Blum Shub]] [[pseudorandom number generator]]. It also yields the [[public key encryption|public key]] [[Goldwasser–Micali cryptosystem]],<ref>{{cite book |author=S. Goldwasser, S. Micali |title=Proceedings of the fourteenth annual ACM symposium on Theory of computing - STOC '82 |chapter=Probabilistic encryption & how to play mental poker keeping secret all partial information |year=1982 |pages=365–377 |doi=10.1145/800070.802212|isbn=0897910702 |s2cid=10316867 }}</ref><ref>{{cite journal |author=S. Goldwasser, S. Micali |title=Probabilistic encryption |journal=Journal of Computer and System Sciences |volume=28 |issue=2 |year=1984 |pages=270–299 |doi=10.1016/0022-0000(84)90070-9|doi-access=free }}</ref> as well as the [[identity based encryption|identity based]] [[Cocks IBE scheme| Cocks scheme]].

==See also==
* [[Higher residuosity problem]]

==References==
{{Reflist}}

{{Computational hardness assumptions}}

[[Category:Computational number theory]]
[[Category:Computational hardness assumptions]]
[[Category:Theory of cryptography]]