El problema de residuosidad cuadrática ( QRP [1] ) en la teoría computacional de números es decidir, dados los números enteros y , ya sea es un módulo de residuo cuadráticoo no. Aquí para dos primos desconocidos y , y se encuentra entre los números que no son evidentemente no 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 dureza , ver § Aplicaciones .
Un algoritmo eficiente para el problema de residuosidad cuadrática implica inmediatamente algoritmos eficientes para otros problemas teóricos de números, como decidir si un compuesto de factorización desconocida es el producto de 2 o 3 primos. [2]
Formulación precisa
Enteros dados y , se dice que es un módulo de residuo cuadrático si existe un entero tal que
- .
De lo contrario, decimos que es un no residuo cuadrático. Cuándoes primo, se acostumbra utilizar el símbolo de Legendre :
Este es un carácter multiplicativo que significa por exactamente de los valores , y es para los restantes.
Es fácil de calcular usando la ley de reciprocidad cuadrática de una manera similar al algoritmo euclidiano , vea el símbolo de Legendre .
Considere ahora algunos dados dónde y son dos primos desconocidos diferentes. Un dado es un módulo de residuo cuadrático si y solo si es un módulo de residuo cuadrático tanto y .
Ya que no sabemos o , no podemos calcular y . Sin embargo, es fácil calcular su producto. Esto se conoce como el símbolo de Jacobi :
Esto también se puede calcular de manera eficiente utilizando la ley de reciprocidad cuadrática para los símbolos de Jacobi.
Sin emabargo, no puede en todos los casos decirnos si es un módulo de residuo cuadrático ¡o no! Más precisamente, si luego es necesariamente un módulo cuadrático sin residuos ya sea o , en cuyo caso hemos terminado. Pero si entonces es el caso que es un módulo de residuo cuadrático tanto y , o un módulo cuadrático sin residuos, ambos y . No podemos distinguir estos casos de saber solo que.
Esto conduce a la formulación precisa del problema de residuos cuadráticos:
Problema: números enteros dados y , dónde y son desconocidos, diferentes primos, y donde , determinar si es un módulo de residuo cuadrático o no.
Distribución de residuos
Si se extrae uniformemente al azar de números enteros tal que , es más a menudo un residuo cuadrático o un módulo cuadrático sin residuo ?
Como se mencionó anteriormente, exactamente la mitad de las opciones de , luego , y para el resto tenemos . Por extensión, esto también se aplica a la mitad de las opciones de. Similarmente para. Del álgebra básica, se deduce que esto divide en 4 partes de igual tamaño, dependiendo del signo de y .
El permitido en el problema de residuo cuadrático dado 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.
Aplicaciones
La intratabilidad del problema de residuosidad 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 .
Ver también
Referencias
- ^ Kaliski, Burt (2011). "Problema de residuo cuadrático". Enciclopedia de criptografía y seguridad : 1003. doi : 10.1007 / 978-1-4419-5906-5_429 .
- ^ Adleman, L. (1980). "Sobre la distinción de números primos de números compuestos". Actas del 21º Simposio del IEEE sobre los fundamentos de la informática (FOCS), Syracuse, NY . págs. 387–408. doi : 10.1109 / SFCS.1980.28 . ISSN 0272-5428 .
- ^ S. Goldwasser, S. Micali (1982). "Cifrado probabilístico y cómo jugar al póquer mental manteniendo en secreto toda la información parcial". Proc. 14º Simposio de Teoría de la Computación : 365–377. doi : 10.1145 / 800070.802212 .
- ^ S. Goldwasser, S. Micali (1984). "Cifrado probabilístico". Revista de Ciencias de la Computación y Sistemas . 28 (2): 270–299. doi : 10.1016 / 0022-0000 (84) 90070-9 .