Problema de residuosidad cuadrática

Problema en la teoría de números computacionales

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). ${\displaystyle a}$ ${\displaystyle N}$ ${\displaystyle a}$ ${\displaystyle N}$ ${\displaystyle N=p_{1}p_{2}}$ ${\displaystyle p_{1}}$ ${\displaystyle p_{2}}$ ${\displaystyle 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] ${\displaystyle N}$

Formulación precisa

Dados los números enteros y , se dice que es un residuo cuadrático módulo si existe un número entero tal que ${\displaystyle a}$ ${\displaystyle T}$ ${\displaystyle a}$ ${\displaystyle T}$ ${\displaystyle 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{ if }}a{\text{ is a quadratic residue modulo }}p{\text{ and }}a\not \equiv 0{\pmod {p}},\\-1&{\text{ if }}a{\text{ is a quadratic non-residue modulo }}p,\\0&{\text{ if }}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 (}{\tfrac {a}{p}}{\big )}=1}$ ${\displaystyle (p-1)/2}$ ${\displaystyle 1,\ldots ,p-1}$ ${\displaystyle -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 datos donde y son dos primos desconocidos diferentes. Un dato es un residuo cuadrático módulo si y solo si es un residuo cuadrático módulo tanto y como . ${\displaystyle N=p_{1}p_{2}}$ ${\displaystyle p_{1}}$ ${\displaystyle p_{2}}$ ${\displaystyle a}$ ${\displaystyle N}$ ${\displaystyle a}$ ${\displaystyle p_{1}}$ ${\displaystyle p_{2}}$ ${\displaystyle \gcd(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 : ${\displaystyle p_{1}}$ ${\displaystyle 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 )}}$ ${\displaystyle a}$ ${\displaystyle N}$ ${\displaystyle {\big (}{\tfrac {a}{N}}{\big )}=-1}$ ${\displaystyle a}$ ${\displaystyle p_{1}}$ ${\displaystyle p_{2}}$ ${\displaystyle {\big (}{\tfrac {a}{N}}{\big )}=1}$ ${\displaystyle a}$ ${\displaystyle p_{1}}$ ${\displaystyle p_{2}}$ ${\displaystyle p_{1}}$ ${\displaystyle p_{2}}$ ${\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 y , donde y son primos desconocidos distintos, y donde , determinar si es un residuo cuadrático módulo o no. ${\displaystyle a}$ ${\displaystyle N=p_{1}p_{2}}$ ${\displaystyle p_{1}}$ ${\displaystyle p_{2}}$ ${\displaystyle {\big (}{\tfrac {a}{N}}{\big )}=1}$ ${\displaystyle a}$ ${\displaystyle N}$

Distribución de residuos

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 ? ${\displaystyle a}$ ${\displaystyle 0,\ldots ,N-1}$ ${\displaystyle {\big (}{\tfrac {a}{N}}{\big )}=1}$ ${\displaystyle a}$ ${\displaystyle 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 (}{\tfrac {a}{p_{1}}}{\big )}=1}$ ${\displaystyle {\big (}{\tfrac {a}{p_{1}}}{\big )}=-1}$ ${\displaystyle a\in \{1,\ldots ,N-1\}\setminus p_{1}\mathbb {Z} }$ ${\displaystyle 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. ${\displaystyle a}$ ${\displaystyle {\big (}{\tfrac {a}{p_{1}}}{\big )}={\big (}{\tfrac {a}{p_{2}}}{\big )}=1}$ ${\displaystyle {\big (}{\tfrac {a}{p_{1}}}{\big )}={\big (}{\tfrac {a}{p_{2}}}{\big )}=-1}$ ${\displaystyle a}$

Aplicaciones

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 .

Véase también

• Problema de mayor residuosidad

Referencias

1. Kaliski, Burt (2011). "Problema de residuosidad cuadrática". Enciclopedia de criptografía y seguridad . p. 1003. doi : 10.1007/978-1-4419-5906-5_429 . ISBN 978-1-4419-5905-8.
2. Adleman, L. (1980). "Sobre la distinción entre números primos y números compuestos". Actas del 21.º Simposio IEEE sobre los fundamentos de la informática (FOCS), Syracuse, NY . pp. 387–408. doi :10.1109/SFCS.1980.28. ISSN  0272-5428.
3. S. Goldwasser, S. Micali (1982). "Cifrado probabilístico y cómo jugar al póquer mental manteniendo en secreto toda la información parcial". Actas del decimocuarto simposio anual de la ACM sobre teoría de la computación - STOC '82 . págs. 365–377. doi :10.1145/800070.802212. ISBN 0897910702. Número de identificación del sujeto  10316867.
4. S. Goldwasser, S. Micali (1984). "Cifrado probabilístico". Revista de Ciencias de la Computación y de Sistemas . 28 (2): 270–299. doi : 10.1016/0022-0000(84)90070-9 .