QR ∈ NP

Inclusion · folklore

Statement

The quadratic residuosity language $\{(N,x):N\text{ odd},x\in {\mathrm{QR}}_N\}$ is in NP: a square root $w$ of $x$ is a witness, checked by $\gcd (x,N)=1$ and $w^2\equiv x(\mathrm{mod}N)$ — folklore.

Notes

• The complement is in $\mathbf{NP}$ as well, with a divisor of $N$ of Jacobi symbol $-1$ as witness: QR ∈ coNP — folklore.