Implementación de algoritmos de teoría de números/Raíz cuadrada modular
Resolver en aritmética modular una congruencia de la forma r2 ≡ n (mod p), donde p es un número primo se conoce como encontrar la raíz cuadrada de n modulo p.
El algoritmo de Tonelli–Shanks (o algoritmo RESSOL) es el más usado. Tonelli–Shanks no puede usarse para módulos compuestos: el encontrar raíces módulo números compuestos es un problema computacional equivalente a la factorización de enteros.[1]
El algoritmo
[editar]Operaciones y comparaciones de elementos del grupo multiplicativo de enteros módulo p son expresadas aquí implícitamente mod p.
Entradas:
- p, un primo
- n, un elemento de tal que las soluciones de la congruencia r2 = n exista; cuando esto se cumpla se dirá que n es un residuo cuadrático mod p.
Salidas:
- r en tal que r2 = n
Algoritmo:
- Factorizando potencia de 2, encontrar Q y S tales que con Q impar
- Buscar un z en que sea un residuo no cuadrático.
- La mitad de los elementos de ese conjunto serán residuos no cuadráticos.
- Los candidatos pueden ser testeados mediante el criterio de Euler o buscando el símbolo de Jacobi.
- Sea
- Bucle:
- Si t = 0, retornar r = 0
- Si t = 1, retornar r = R
- De lo contrario, use el cuadrado repetidamente para encontrar el mínimo i, 0 < i < M, tal que
- Sea , y establezca
Una vez que haya resuelto la congruencia con r, la segunda solución es . Si la última i tal que es M, entonces no existe una solución a la congruencia, ie n no es un residuo cuadrático.
Esto es más útil cuando p ≡ 1 (mod 4). Para primos tales que p ≡ 3 (mod 4), este problema tienes las posibles soluciones . Si esas satisfacen que , esas son las únicas soluciones. Si no, , n es un residuo no cuadrático y no hay soluciones
Referencias
[editar]- ↑ Oded Goldreich, Computational complexity: a conceptual perspective, Cambridge University Press, 2008, p. 588.