Problema de la resiliencia cuadrática

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

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 dificultad ; véase la sección  Aplicaciones .

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

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

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

De lo contrario, decimos que es un no residuo cuadrático. Cuando${\displaystyle T=p}$es un número primo, es costumbre usar el símbolo de Legendre :

${\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${\displaystyle {\big (}{\tfrac {a}{p}}{\big )}=1}$para exactamente${\displaystyle (p-1)/2}$de los valores${\displaystyle 1,\ldots ,p-1}$, y es${\displaystyle -1}$para el resto.

Es fácil calcularlo utilizando la ley de reciprocidad cuadrática de una manera similar al algoritmo euclidiano ; véase el símbolo de Legendre .

Consideremos ahora algunos datos dados${\displaystyle N=p_{1}p_{2}}$dónde${\displaystyle p_{1}}$y${\displaystyle p_{2}}$son dos primos desconocidos diferentes. Un dado${\displaystyle a}$es un residuo cuadrático módulo${\displaystyle N}$si y solo si${\displaystyle a}$es un residuo cuadrático módulo ambos${\displaystyle p_{1}}$y${\displaystyle p_{2}}$y${\displaystyle \gcd(a,N)=1}$.

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

${\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,${\displaystyle {\big (}{\tfrac {a}{N}}{\big )}}$no puede decirnos en todos los casos si${\displaystyle a}$es un residuo cuadrático módulo${\displaystyle N}$¡O no! Más precisamente, si${\displaystyle {\big (}{\tfrac {a}{N}}{\big )}=-1}$entonces${\displaystyle a}$es necesariamente un no residuo cuadrático módulo o${\displaystyle p_{1}}$o${\displaystyle p_{2}}$, en cuyo caso hemos terminado. Pero si${\displaystyle {\big (}{\tfrac {a}{N}}{\big )}=1}$entonces es el caso que${\displaystyle a}$es un residuo cuadrático módulo ambos${\displaystyle p_{1}}$y${\displaystyle p_{2}}$o un no residuo cuadrático módulo ambos${\displaystyle p_{1}}$y${\displaystyle p_{2}}$No podemos distinguir estos casos sabiendo solo eso.${\displaystyle {\big (}{\tfrac {a}{N}}{\big )}=1}$.

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

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

Si${\displaystyle a}$se extrae uniformemente al azar de entre los números enteros${\displaystyle 0,\ldots ,N-1}$de tal manera que${\displaystyle {\big (}{\tfrac {a}{N}}{\big )}=1}$, es${\displaystyle a}$más a menudo un residuo cuadrático o un no residuo cuadrático módulo${\displaystyle N}$¿

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

Lo permitido${\displaystyle a}$en el problema del residuo cuadrático dado como arriba constituyen exactamente esas dos partes correspondientes a los casos${\displaystyle {\big (}{\tfrac {a}{p_{1}}}{\big )}={\big (}{\tfrac {a}{p_{2}}}{\big )}=1}$y${\displaystyle {\big (}{\tfrac {a}{p_{1}}}{\big )}={\big (}{\tfrac {a}{p_{2}}}{\big )}=-1}$. En consecuencia, exactamente la mitad de las posibles${\displaystyle a}$son residuos cuadráticos y los restantes no lo son.

La intratabilidad del problema de la residuo cuadrática es la base de la seguridad del generador de números pseudoaleatorios 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 desigualdad