4
$\begingroup$

Quadratic reciprocity 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?

  • 1
    Seems you are right to me. Note that verifying a prime factorization consists of not only verifying that the product is $n$, but also verifying that the claimed factors are indeed prime. But this can be done in polynomial time.2011-10-10

1 Answers 1

2

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.