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

Resolver en aritmética modular una congruencia de la forma r² ≡ 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.

El algoritmo

Operaciones y comparaciones de elementos del grupo multiplicativo de enteros módulo p $(\mathbb {Z} /p\mathbb {Z} )^{\times }$ son expresadas aquí implícitamente mod p.

Entradas:

• p, un primo
• n, un elemento de $\mathbb {Z} /p\mathbb {Z}$ tal que las soluciones de la congruencia r² = n exista; cuando esto se cumpla se dirá que n es un residuo cuadrático mod p.

Salidas:

• r en $\mathbb {Z} /p\mathbb {Z}$ tal que r² = n

Algoritmo:

1. Factorizando potencia de 2, encontrar Q y S tales que $p-1=Q2^{S}$ con Q impar
2. Buscar un z en $\mathbb {Z} /p\mathbb {Z}$ 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

   ${\begin{aligned}M&\leftarrow S\\c&\leftarrow z^{Q}\\t&\leftarrow n^{Q}\\R&\leftarrow n^{\frac {Q+1}{2}}\end{aligned}}$

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 $t^{2^{i}}=1$
   • Sea $b\leftarrow c^{2^{M-i-1}}$, y establezca

     ${\begin{aligned}M&\leftarrow i\\c&\leftarrow b^{2}\\t&\leftarrow tb^{2}\\R&\leftarrow Rb\end{aligned}}$

Una vez que haya resuelto la congruencia con r, la segunda solución es $-r{\pmod {p}}$. Si la última i tal que $t^{2^{i}}=1$ 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 $r=\pm n^{\frac {p+1}{4}}{\pmod {p}}$. Si esas satisfacen que $r^{2}\equiv n{\pmod {p}}$, esas son las únicas soluciones. Si no, $r^{2}\equiv -n{\pmod {p}}$, n es un residuo no cuadrático y no hay soluciones