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=Q{2}^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{array}{cc}M& \leftarrow S\\ c& \leftarrow z^Q\\ t& \leftarrow n^Q\\ R& \leftarrow n^{\frac{Q+1}{2}}\end{array}$

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{array}{cc}M& \leftarrow i\\ c& \leftarrow b^2\\ t& \leftarrow t{b}^2\\ R& \leftarrow Rb\end{array}$

Una vez que haya resuelto la congruencia con r, la segunda solución es $-r(\mathrm{mod}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}}(\mathrm{mod}p)$. Si esas satisfacen que $r^2\equiv n(\mathrm{mod}p)$, esas son las únicas soluciones. Si no, $r^2\equiv -n(\mathrm{mod}p)$, n es un residuo no cuadrático y no hay soluciones