Problema de residuosidad cuadrática

---

El problema de residuosidad cuadrática ( QRP ^[1] ) en la teoría computacional de números consiste en decidir, dados números enteros y , si es un módulo de residuo cuadrático o no. Aquí , para dos primos desconocidos y , y se encuentra entre los números que obviamente no son residuos cuadráticos (ver más abajo).${\ estilo de visualización a}$${\ estilo de visualización N}$${\ estilo de visualización a}$${\ estilo de visualización N}$${\displaystyle N=p_{1}p_{2}}$${\displaystyle p_{1}}$${\displaystyle p_{2}}$${\ estilo de visualización a}$

El problema fue descrito por primera vez por Gauss en sus Disquisitiones Arithmeticae en 1801. Se cree que este problema es computacionalmente difícil . Varios métodos criptográficos se basan en su dureza , ver § Aplicaciones .

Un algoritmo eficiente para el problema de residuosidad cuadrática implica inmediatamente algoritmos eficientes para otros problemas de teoría de números, como decidir si un compuesto de factorización desconocida es el producto de 2 o 3 primos. ^[2]${\ estilo de visualización N}$

Dados los números enteros y , se dice que es un módulo de residuo cuadrático si existe un número entero tal que${\ estilo de visualización a}$${\ estilo de visualización T}$${\ estilo de visualización a}$${\ estilo de visualización T}$${\ estilo de visualización b}$

En caso contrario decimos que es un no residuo cuadrático. Cuando es primo, se acostumbra utilizar el símbolo de Legendre :${\ estilo de visualización T = p}$

Este es un carácter multiplicativo que significa exactamente de los valores , y es para el resto.${\displaystyle {\grande (}{\tfrac {a}{p}}{\grande)}=1}$${\ estilo de visualización (p-1)/2}$${\ estilo de visualización 1, \ ldots, p-1}$${\ estilo de visualización -1}$

---