¿Es problema de la reciprocidad cuadrática en la coNP?

Question

La reciprocidad cuadrática es en $\mathsf{NP}$, ya que para demostrar $x$ es residuo cuadrático usted puede mostrar a $y$ tal que $y^2=x$.

Wikipedia reclamaciones que el problema está en $\mathsf{coNP}$. Este libro afirma que no se conoce. Es?

Se parece a:

• Al $n$ es primo, se puede utilizar de Euler criterio por lo que el problema está en $\mathsf{P}$,
• En el caso general se puede dar de la factorización de $n$ y reducir el problema a $n=p^k$.

Estoy en lo cierto?

Answer 1

Creo que estás en lo correcto.

Primero de todos, el armario puede proporcionar la factorización prima de $n$, por lo que sin pérdida de generalidad supongamos $n = p^k$ algunos $k$. Así, hemos reducido el problema a la primer poderes.

Estoy tomando los siguientes conjuntos de reglas para determinar si un número es un residuo cuadrático o no el modulo $p^k$ desde esta página de la wikipedia. Tenga cuidado en la lectura de la página de la wikipedia, ya que utiliza una notación diferente que en la pregunta.

Si el módulo es $p^k$, $p^x A$

• es un residuo modulo $p^k$ si $x \geq k$
• es un nonresidue modulo $p^k$ si $x < k$ es impar
• es un residuo modulo $p^k$ si $x < k$ es incluso y $A$ es un residuo modulo $p$
• es un nonresidue modulo $p^k$ si $x < k$ es incluso y $A$ es un nonresidue modulo $p$.

Y para $p=2$:

Todos los impares plazas se $\equiv 1 \pmod 8$ y, a fortiori,$\equiv 1 \pmod 4$. Si $a$ es un número impar y $m = 8, 16$, o algún poder superior de $2$, $a$ es un residuo modulo $m$ si y sólo si $a \equiv 1 \pmod 8$.

Por lo que un número distinto de cero es un residuo modulo $8, 16$, etc., si y sólo si es de la forma $4^x(8y + 1)$.

Así que finalmente se reduce al caso de la comprobación de si un número dado es un residuo cuadrático o nonresidue modulo de un primer $p$. Pero como el OP notas, que se puede hacer fácilmente en determinista polinomio de tiempo utilizando el criterio de Euler.