QR ∈ coNP

Inclusion · folklore

Statement

The quadratic residuosity language $\{(N,x):N\text{ odd},x\in {\mathrm{QR}}_N\}$ is in coNP. If $\gcd (x,N)>1$, non-membership is checked directly; otherwise a divisor $d$ of $N$ with Jacobi symbol $\left(\frac{x}{d}\right)=-1$ certifies $x\notin {\mathrm{QR}}_N$, and such a $d$ exists for every non-residue. No primality certificate is needed — folklore. Hence quadratic residuosity is in $\mathbf{NP}\cap \mathbf{coNP}$ (QR ∈ NP) and is not $\mathbf{NP}$-hard under Cook reductions unless $\mathbf{NP}=\mathbf{coNP}$ — standard.

Sketch

For odd $N$ and $x$ coprime to $N$, $x$ is a square modulo $N$ iff it is a square modulo every prime $p\mid N$, by the Chinese remainder theorem and Hensel’s lemma; a non-residue therefore has Legendre symbol $\left(\frac{x}{p}\right)=-1$ for some prime $p\mid N$, and $d=p$ is a certificate. Conversely, $\left(\frac{x}{d}\right)$ is the product of the Legendre symbols of $x$ over the prime factors of $d$ with multiplicity, so $\left(\frac{x}{d}\right)=-1$ forces $\left(\frac{x}{p}\right)=-1$ for some prime $p\mid d\mid N$, and $x$ is not a square modulo $N$. The Jacobi symbol is computed in polynomial time by quadratic reciprocity without factoring $d$ — standard.

Notes

• Both the language and its complement among Jacobi-symbol-one elements have perfect zero-knowledge proofs: QR ∈ SZK — GMR85.