Problema de residuosidad cuadrática

El problema de residuosidad cuadrática ( QRP ^[1] ) en la teoría de números computacionales consiste en decidir, dados los números enteros y , si es un residuo cuadrático módulo o no. Aquí, para dos primos desconocidos y , y se encuentra entre los números que no son obviamente residuos cuadráticos no (ver más abajo). ${\estilo de visualización a}$${\estilo de visualización N}$${\estilo de visualización a}$ ${\estilo de visualización N}$$Estilo de visualización N=p_{1}p_{2}}$ $estilo de visualización p_{1}}$$estilo de visualización 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 dependen de su dificultad , consulte § 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 residuo cuadrático módulo 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}$

${\displaystyle a\equiv b^{2}{\pmod {T}}}$.

De lo contrario, decimos que es un residuo cuadrático no restablecido. Cuando es un primo, se acostumbra a utilizar el símbolo de Legendre : ${\displaystyle T=p}$

${\displaystyle \left({\frac {a}{p}}\right)={\begin{cases}1&{\text{ si }}a{\text{ es un residuo cuadrático módulo }}p{\text{ y }}a\not \equiv 0{\pmod {p}},\\-1&{\text{ si }}a{\text{ es un no residuo cuadrático módulo }}p,\\0&{\text{ si }}a\equiv 0{\pmod {p}}.\end{cases}}}$

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

Es fácil de calcular utilizando la ley de reciprocidad cuadrática de manera similar al algoritmo euclidiano ; consulte el símbolo de Legendre .

Consideremos ahora algunos números dados donde y son dos primos desconocidos diferentes. Un número dado es un residuo cuadrático módulo si y solo si es un residuo cuadrático módulo tanto y como . $Estilo de visualización N=p_{1}p_{2}}$$estilo de visualización p_{1}}$$estilo de visualización p_{2}$${\estilo de visualización a}$${\estilo de visualización N}$ ${\estilo de visualización a}$$estilo de visualización p_{1}}$$estilo de visualización p_{2}$${\displaystyle \mcd(a,N)=1}$

Como no sabemos o , no podemos calcular y . Sin embargo, es fácil calcular su producto. Esto se conoce como el símbolo de Jacobi : $estilo de visualización p_{1}}$$estilo de visualización p_{2}$${\displaystyle {\big (}{\tfrac {a}{p_{1}}}{\big )}}$${\displaystyle {\big (}{\tfrac {a}{p_{2}}}{\big )}}$

${\displaystyle \left({\frac {a}{N}}\right)=\left({\frac {a}{p_{1}}}\right)\left({\frac {a}{p_{2}}}\right)}$

Esto también se puede calcular de manera eficiente utilizando la ley de reciprocidad cuadrática para los símbolos de Jacobi.

Sin embargo, no puede decirnos en todos los casos si es un residuo cuadrático módulo o no. Más precisamente, si entonces es necesariamente un no residuo cuadrático módulo o bien o bien , en cuyo caso hemos terminado. Pero si entonces es el caso de que es un residuo cuadrático módulo tanto y , o un no residuo cuadrático módulo tanto y . No podemos distinguir estos casos sabiendo simplemente que . ${\displaystyle {\big (}{\tfrac {a}{N}}{\big )}}$${\estilo de visualización a}$${\estilo de visualización N}$${\displaystyle {\big (}{\frac {a}{N}}{\big )}=-1}$${\estilo de visualización a}$$estilo de visualización p_{1}}$$estilo de visualización p_{2}$${\displaystyle {\big (}{\frac {a}{N}}{\big )}=1}$${\estilo de visualización a}$$estilo de visualización p_{1}}$$estilo de visualización p_{2}$$estilo de visualización p_{1}}$$estilo de visualización p_{2}$${\displaystyle {\big (}{\frac {a}{N}}{\big )}=1}$

Esto conduce a la formulación precisa del problema del residuo cuadrático:

Problema: Dados los números enteros y , donde y son primos desconocidos distintos, y donde , determinar si es un residuo cuadrático módulo o no. ${\estilo de visualización a}$$Estilo de visualización N=p_{1}p_{2}}$$estilo de visualización p_{1}}$$estilo de visualización p_{2}$${\displaystyle {\big (}{\frac {a}{N}}{\big )}=1}$${\estilo de visualización a}$${\estilo de visualización N}$

Si se extrae de manera uniforme al azar de números enteros tales que , es más a menudo un residuo cuadrático o un no residuo cuadrático módulo ? ${\estilo de visualización a}$${\displaystyle 0,\ldots ,N-1}$${\displaystyle {\big (}{\frac {a}{N}}{\big )}=1}$${\estilo de visualización a}$${\estilo de visualización N}$

Como se mencionó anteriormente, para exactamente la mitad de las opciones de , entonces , y para el resto tenemos . Por extensión, esto también es válido para la mitad de las opciones de . De manera similar para . Del álgebra básica, se deduce que esto se divide en 4 partes de igual tamaño, dependiendo del signo de y . ${\displaystyle a\in \{1,\ldots ,p_{1}-1\}}$${\displaystyle {\big (}{\frac {a}{p_{1}}}{\big )}=1}$${\displaystyle {\big (}{\frac {a}{p_{1}}}{\big )}=-1}$${\displaystyle a\in \{1,\ldots ,N-1\}\setminus p_{1}\mathbb {Z} }$$estilo de visualización p_{2}$${\displaystyle (\mathbb {Z} /N\mathbb {Z} )^{\times }}$${\displaystyle {\big (}{\tfrac {a}{p_{1}}}{\big )}}$${\displaystyle {\big (}{\tfrac {a}{p_{2}}}{\big )}}$

Los permitidos en el problema de residuos cuadráticos dados anteriormente constituyen exactamente las dos partes correspondientes a los casos y . En consecuencia, exactamente la mitad de los posibles son residuos cuadráticos y el resto no lo son. ${\estilo de visualización a}$${\displaystyle {\big (}{\frac {a}{p_{1}}}{\big )}={\big (}{\frac {a}{p_{2}}}{\big )}=1}$${\displaystyle {\big (}{\frac {a}{p_{1}}}{\big )}={\big (}{\frac {a}{p_{2}}}{\big )}=-1}$${\estilo de visualización a}$

La intratabilidad del problema de residuosidad cuadrática es la base de la seguridad del generador de números pseudoaleatorios de Blum Blum Shub . También produce el criptosistema de clave pública Goldwasser–Micali ^{[3] [4]} , así como el esquema Cocks basado en identidad .

• Problema de mayor residuosidad