Is quadratic residuosity problem in coNP?

Question

Quadratic residuosity is in $\mathsf{NP}$, since to prove $x$ is quadratic residue you can show $y$ such that $y^2=x$.

Wikipedia claims the problem is in $\mathsf{coNP}$. This book claims it is not known. Is it?

It seems at:

• When $n$ is prime, one can use Euler's criterion so the problem is in $\mathsf{P}$,
• In general case one can give factorization of $n$ and reduce the problem to $n=p^k$.

Am I correct?

Answer 1

I think you are correct.

First of all, the prover can provide the prime factorization of $n$, so without loss of generality assume $n = p^k$ for some $k$. We have thus reduced the problem to the prime powers.

I am taking the following sets of rules for determining if a number is a quadratic residue or not modulo $p^k$ from this wikipedia page. Be careful in reading the wikipedia page since it uses a different notation than in the question.

If the modulus is $p^k$, then $p^x A$

• is a residue modulo $p^k$ if $x \geq k$
• is a nonresidue modulo $p^k$ if $x < k$ is odd
• is a residue modulo $p^k$ if $x < k$ is even and $A$ is a residue modulo $p$
• is a nonresidue modulo $p^k$ if $x < k$ is even and $A$ is a nonresidue modulo $p$.

And for $p=2$:

All odd squares are $\equiv 1 \pmod 8$ and a fortiori $\equiv 1 \pmod 4$. If $a$ is an odd number and $m = 8, 16$, or some higher power of $2$, then $a$ is a residue modulo $m$ if and only if $a \equiv 1 \pmod 8$.

So a nonzero number is a residue modulo $8, 16$, etc., if and only if it is of the form $4^x(8y + 1)$.

So we are finally reduced to the case of checking whether a given number is a quadratic residue or nonresidue modulo a prime $p$. But as the OP notes, that can be easily done in deterministic polynomial time using Euler's criterion.