Ir al contenido

Implementación de algoritmos de teoría de números/Raíz cuadrada modular

De Wikilibros, la colección de libros de texto de contenido libre.

Resolver en aritmética modular una congruencia de la forma r2n (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:

  1. Factorizando potencia de 2, encontrar Q y S tales que con Q impar
  2. 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.
  3. Sea
  4. 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]
  1. Oded Goldreich, Computational complexity: a conceptual perspective, Cambridge University Press, 2008, p. 588.