Algoritmo de Tonelli-Shanks

El algoritmo de Tonelli-Shanks (conocido por Shanks como el algoritmo RESSOL) se utiliza en aritmética modular para resolver r en una congruencia de la forma r ² ≡ n (mod p ), donde p es un primo : es decir, para encontrar una raíz cuadrada de n módulo p .

El algoritmo de Tonelli-Shanks no se puede utilizar para módulos compuestos: encontrar raíces cuadradas módulo números compuestos es un problema computacional equivalente a la factorización de enteros . ^{[ 1 ]}

Alberto Tonelli ^{[ 2 ] [ 3 ]} desarrolló en 1891 una versión equivalente, aunque ligeramente más redundante, de este algoritmo. La versión que se analiza aquí fue desarrollada independientemente por Daniel Shanks en 1973, quien explicó:

Mi tardanza en conocer estas referencias históricas se debió a que le presté el Volumen 1 de la Historia de Dickson a un amigo y nunca me lo devolvió. ^{[ 4 ]}

Según Dickson, ^{[ 3 ]} el algoritmo de Tonelli puede tomar raíces cuadradas de x módulo potencias primas p ^λ aparte de los números primos.

Dado un valor distinto de cero${\displaystyle n}$y un primo${\displaystyle p>2}$(que siempre será impar), el criterio de Euler nos dice que${\displaystyle n}$tiene raíz cuadrada (es decir,${\displaystyle n}$es un residuo cuadrático ) si y solo si :

${\displaystyle n^{\frac {p-1}{2}}\equiv 1{\pmod {p}}}$.

Por el contrario, si un número${\displaystyle z}$Si no tiene raíz cuadrada (es un no residuo), el criterio de Euler nos dice que:

${\displaystyle z^{\frac {p-1}{2}}\equiv -1{\pmod {p}}}$.

No es difícil encontrar tal cosa${\displaystyle z}$, porque la mitad de los enteros entre 1 y${\displaystyle p-1}$poseen esta propiedad. Por lo tanto, asumimos que tenemos acceso a dicho no residuo.

Al dividir (normalmente) repetidamente por 2, podemos escribir${\displaystyle p-1}$como${\displaystyle Q2^{S}}$, dónde${\displaystyle Q}$es extraño. Tenga en cuenta que si lo intentamos

${\displaystyle R\equiv n^{\frac {Q+1}{2}}{\pmod {p}}}$,

entonces${\displaystyle R^{2}\equiv n^{Q+1}=(n)(n^{Q}){\pmod {p}}}$. Si${\displaystyle t\equiv n^{Q}\equiv 1{\pmod {p}}}$, entonces${\displaystyle R}$es una raíz cuadrada de${\displaystyle n}$. De lo contrario, para${\displaystyle M=S}$, tenemos${\displaystyle R}$y${\displaystyle t}$satisfactorio:

• ${\displaystyle R^{2}\equiv nt{\pmod {p}}}$; y
• ${\displaystyle t}$es un${\displaystyle 2^{M-1}}$raíz -ésima de 1 (porque${\displaystyle t^{2^{M-1}}=t^{2^{S-1}}\equiv n^{Q2^{S-1}}=n^{\frac {p-1}{2}}}$).

Si, dada la elección de${\displaystyle R}$y${\displaystyle t}$para un caso particular${\displaystyle M}$satisfaciendo lo anterior (donde${\displaystyle R}$no es una raíz cuadrada de${\displaystyle n}$), podemos calcular fácilmente otro${\displaystyle R}$y${\displaystyle t}$para${\displaystyle M-1}$De modo que se cumplan las relaciones anteriores, podemos repetir esto hasta${\displaystyle t}$se convierte en un${\displaystyle 2^{0}}$raíz -ésima de 1, es decir,${\displaystyle t=1}$En ese momento${\displaystyle R}$es una raíz cuadrada de${\displaystyle n}$.

Podemos comprobar si${\displaystyle t}$es un${\displaystyle 2^{M-2}}$raíz -ésima de 1 elevándolo al cuadrado${\displaystyle M-2}$veces y comprobar si es 1. Si lo es, entonces no necesitamos hacer nada, ya que la misma elección de${\displaystyle R}$y${\displaystyle t}$funciona. Pero si no funciona,${\displaystyle t^{2^{M-2}}}$debe ser -1 (porque al elevarlo al cuadrado da 1, y solo puede haber dos raíces cuadradas 1 y -1 de 1 módulo${\displaystyle p}$).

Para encontrar un nuevo par de${\displaystyle R}$y${\displaystyle t}$podemos multiplicar${\displaystyle R}$por un factor${\displaystyle b}$, por determinar. Entonces${\displaystyle t}$debe multiplicarse por un factor${\displaystyle b^{2}}$para mantener${\displaystyle R^{2}\equiv nt{\pmod {p}}}$Entonces, cuando${\displaystyle t^{2^{M-2}}}$es -1, necesitamos encontrar un factor${\displaystyle b^{2}}$de modo que${\displaystyle tb^{2}}$es un${\displaystyle 2^{M-2}}$raíz -ésima de 1, o equivalentemente${\displaystyle b^{2}}$es un${\displaystyle 2^{M-2}}$-ésima raíz de -1.

El truco aquí es hacer uso de${\displaystyle z}$, el no residuo conocido. El criterio de Euler aplicado a${\displaystyle z}$Lo que se muestra arriba dice que${\displaystyle z^{Q}}$es un${\displaystyle 2^{S-1}}$-ésima raíz de -1. Entonces, al elevar al cuadrado${\displaystyle z^{Q}}$repetidamente, tenemos acceso a una secuencia de${\displaystyle 2^{i}}$raíces -ésimas de -1. Podemos seleccionar la correcta para que sirva como${\displaystyle b}$Con un poco de mantenimiento de variables y una compresión de casos trivial, el siguiente algoritmo surge de forma natural.

Operaciones y comparaciones sobre elementos del grupo multiplicativo de enteros módulo p${\displaystyle \mathbb {Z} /p\mathbb {Z} }$son implícitamente módulo p .

Entradas :

• p , un primo
• n , un elemento de${\displaystyle \mathbb {Z} /p\mathbb {Z} }$de tal manera que existan soluciones a la congruencia r ² = n ; cuando esto es así, decimos que n es un residuo cuadrático módulo p .

Resultados :

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

Algoritmo :

1. Al factorizar potencias de 2, encuentre Q y S tales que${\displaystyle p-1=Q2^{S}}$con Q impar
2. Buscar una z en${\displaystyle \mathbb {Z} /p\mathbb {Z} }$que es un no residuo cuadrático
   • La mitad de los elementos del conjunto serán no residuos cuadráticos.
   • Los candidatos pueden ser evaluados con el criterio de Euler o mediante la búsqueda del símbolo de Jacobi.
3. Dejar

   ${\displaystyle {\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, devuelve r = 0.
   • Si t = 1, devuelve r = R
   • De lo contrario, utilice la elevación al cuadrado repetida para encontrar el menor i , 0 < i < M , tal que${\displaystyle t^{2^{i}}=1}$
   • Dejar${\displaystyle b\leftarrow c^{2^{M-i-1}}}$y establecer

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

Una vez que hayas resuelto la congruencia con r, la segunda solución es${\displaystyle -r{\pmod {p}}}$. Si el menor i tal que${\displaystyle t^{2^{i}}=1}$Si M es , entonces no existe solución a la congruencia, es decir, n no es un residuo cuadrático.

Esto es más útil cuando p ≡ 1 (mod 4).

Para números primos tales que p ≡ 3 (mod 4), este problema tiene posibles soluciones.${\displaystyle r=\pm n^{\frac {p+1}{4}}{\pmod {p}}}$. Si estos se cumplen${\displaystyle r^{2}\equiv n{\pmod {p}}}$, son las únicas soluciones. Si no,${\displaystyle r^{2}\equiv -n{\pmod {p}}}$, n es un no residuo cuadrático y no hay soluciones.

Podemos demostrar que al inicio de cada iteración del bucle se cumplen las siguientes invariantes :

• ${\displaystyle c^{2^{M-1}}=-1}$
• ${\displaystyle t^{2^{M-1}}=1}$
• ${\displaystyle R^{2}=tn}$

Inicialmente:

• ${\displaystyle c^{2^{M-1}}=z^{Q2^{S-1}}=z^{\frac {p-1}{2}}=-1}$(ya que z es un no residuo cuadrático, según el criterio de Euler)
• ${\displaystyle t^{2^{M-1}}=n^{Q2^{S-1}}=n^{\frac {p-1}{2}}=1}$(ya que n es un residuo cuadrático)
• ${\displaystyle R^{2}=n^{Q+1}=tn}$

En cada iteración, con M' , c' , t' , R' los nuevos valores reemplazando a M , c , t , R :

• ${\displaystyle c'^{2^{M'-1}}=(b^{2})^{2^{i-1}}=c^{2^{M-i}2^{i-1}}=c^{2^{M-1}}=-1}$
• ${\displaystyle t'^{2^{M'-1}}=(tb^{2})^{2^{i-1}}=t^{2^{i-1}}b^{2^{i}}=-1\cdot -1=1}$
  • ${\displaystyle t^{2^{i-1}}=-1}$ya que tenemos eso${\displaystyle t^{2^{i}}=1}$pero${\displaystyle t^{2^{i-1}}\neq 1}$( i es el valor más pequeño tal que${\displaystyle t^{2^{i}}=1}$)
  • ${\displaystyle b^{2^{i}}=c^{2^{M-i-1}2^{i}}=c^{2^{M-1}}=-1}$
• ${\displaystyle R'^{2}=R^{2}b^{2}=tnb^{2}=t'n}$

De${\displaystyle t^{2^{M-1}}=1}$y la prueba contra t = 1 al comienzo del bucle, vemos que siempre encontraremos un i en 0 < i < M tal que${\displaystyle t^{2^{i}}=1}$. M es estrictamente menor en cada iteración, y por lo tanto el algoritmo tiene garantizado detenerse. Cuando alcanzamos la condición t = 1 y nos detenemos, el último invariante del bucle implica que R ² = n .

Resolviendo la congruencia r ² ≡ 5 (mod 41). 41 es primo como se requiere y 41 ≡ 1 (mod 4). 5 es un residuo cuadrático según el criterio de Euler:${\displaystyle 5^{\frac {41-1}{2}}=5^{20}=1}$(como antes, operaciones en${\displaystyle (\mathbb {Z} /41\mathbb {Z} )^{\times }}$son implícitamente módulo 41).

1. ${\displaystyle p-1=40=5\cdot 2^{3}}$entonces${\displaystyle Q\leftarrow 5}$,${\displaystyle S\leftarrow 3}$
2. Encuentra un valor para z:
   • ${\displaystyle 2^{\frac {41-1}{2}}=1}$, por lo tanto, 2 es un residuo cuadrático según el criterio de Euler.
   • ${\displaystyle 3^{\frac {41-1}{2}}=40=-1}$, por lo tanto, 3 es un no residuo cuadrático: conjunto${\displaystyle z\leftarrow 3}$
3. Colocar
   • ${\displaystyle M\leftarrow S=3}$
   • ${\displaystyle c\leftarrow z^{Q}=3^{5}=38}$
   • ${\displaystyle t\leftarrow n^{Q}=5^{5}=9}$
   • ${\displaystyle R\leftarrow n^{\frac {Q+1}{2}}=5^{\frac {5+1}{2}}=2}$
4. Bucle:
   • Primera iteración:
     • ${\displaystyle t\neq 1}$, así que no hemos terminado
     • ${\displaystyle t^{2^{1}}=40}$,${\displaystyle t^{2^{2}}=1}$entonces${\displaystyle i\leftarrow 2}$
     • ${\displaystyle b\leftarrow c^{2^{M-i-1}}=38^{2^{3-2-1}}=38}$
     • ${\displaystyle M\leftarrow i=2}$
     • ${\displaystyle c\leftarrow b^{2}=38^{2}=9}$
     • ${\displaystyle t\leftarrow tb^{2}=9\cdot 9=40}$
     • ${\displaystyle R\leftarrow Rb=2\cdot 38=35}$
   • Segunda iteración:
     • ${\displaystyle t\neq 1}$, así que todavía no hemos terminado
     • ${\displaystyle t^{2^{1}}=1}$entonces${\displaystyle i\leftarrow 1}$
     • ${\displaystyle b\leftarrow c^{2^{M-i-1}}=9^{2^{2-1-1}}=9}$
     • ${\displaystyle M\leftarrow i=1}$
     • ${\displaystyle c\leftarrow b^{2}=9^{2}=40}$
     • ${\displaystyle t\leftarrow tb^{2}=40\cdot 40=1}$
     • ${\displaystyle R\leftarrow Rb=35\cdot 9=28}$
   • Tercera iteración:
     • ${\displaystyle t=1}$y hemos terminado; regresar${\displaystyle r=R=28}$

En efecto, ^28² ≡ 5 (mod 41) y (−28) ^² ≡ ^13² ≡ 5 (mod 41). Por lo tanto, el algoritmo produce las dos soluciones a nuestra congruencia.

El algoritmo de Tonelli-Shanks requiere (en promedio sobre todas las entradas posibles (residuos cuadráticos y no residuos cuadráticos))

${\displaystyle 2m+2k+{\frac {S(S-1)}{4}}+{\frac {1}{2^{S-1}}}-9}$

multiplicaciones modulares, donde${\displaystyle m}$es el número de dígitos en la representación binaria de${\displaystyle p}$y${\displaystyle k}$es el número de unos en la representación binaria de${\displaystyle p}$. Si el no residuo cuadrático requerido${\displaystyle z}$se puede encontrar comprobando si un número tomado al azar${\displaystyle y}$es un no residuo cuadrático, requiere (en promedio)${\displaystyle 2}$cálculos del símbolo de Legendre . ^{[ 5 ]} El promedio de dos cálculos del símbolo de Legendre se explica de la siguiente manera:${\displaystyle y}$es un residuo cuadrático con probabilidad${\displaystyle {\tfrac {\tfrac {p+1}{2}}{p}}={\tfrac {1+{\tfrac {1}{p}}}{2}}}$, que es más pequeño que${\displaystyle 1}$pero${\displaystyle \geq {\tfrac {1}{2}}}$, por lo que en promedio necesitaremos comprobar si un${\displaystyle y}$es un residuo cuadrático dos veces.

Esto demuestra esencialmente que el algoritmo de Tonelli-Shanks funciona muy bien si el módulo${\displaystyle p}$es aleatorio, es decir, si${\displaystyle S}$no es particularmente grande con respecto al número de dígitos en la representación binaria de${\displaystyle p}$. Como se escribió anteriormente, el algoritmo de Cipolla funciona mejor que el de Tonelli-Shanks si (y solo si)${\displaystyle S(S-1)>8m+20}$Sin embargo, si en cambio se utiliza el algoritmo de Sutherland para realizar el cálculo del logaritmo discreto en el subgrupo 2-Sylow de${\displaystyle \mathbb {F} _{p}^{\ast }}$, uno puede reemplazar${\displaystyle S(S-1)}$con una expresión que está asintóticamente acotada por${\displaystyle O(S\log S/\log \log S)}$. ^{[ 6 ]} Explícitamente, se calcula${\displaystyle e}$de tal manera que${\displaystyle c^{e}\equiv n^{Q}}$y luego${\displaystyle R\equiv c^{-e/2}n^{(Q+1)/2}}$Satisface${\displaystyle R^{2}\equiv n}$(tenga en cuenta que${\displaystyle e}$es un múltiplo de 2 porque${\displaystyle n}$es un residuo cuadrático).

El algoritmo requiere que encontremos un no residuo cuadrático.${\displaystyle z}$No se conoce ningún algoritmo determinista que se ejecute en tiempo polinomial para encontrar tal cosa.${\displaystyle z}$Sin embargo, si la hipótesis generalizada de Riemann es verdadera, existe un no residuo cuadrático.${\displaystyle z<2\ln ^{2}{p}}$, ^{[ 7 ]} lo que permite comprobar cada${\displaystyle z}$hasta ese límite y encontrar uno adecuado${\displaystyle z}$en tiempo polinomial . Sin embargo, tenga en cuenta que este es el peor escenario posible; en general,${\displaystyle z}$Se encuentra en un promedio de 2 ensayos como se indicó anteriormente.

El algoritmo de Tonelli-Shanks puede utilizarse (naturalmente) para cualquier proceso en el que se requieran raíces cuadradas módulo un número primo. Por ejemplo, puede emplearse para hallar puntos en curvas elípticas . También resulta útil para los cálculos del algoritmo de la signatura de Rabin y en la etapa de cribado de la criba cuadrática .

Tonelli–Shanks se puede generalizar a cualquier grupo cíclico (en lugar de${\displaystyle (\mathbb {Z} /p\mathbb {Z} )^{\times }}$) y a las raíces k -ésimas para un entero k arbitrario , en particular a tomar la raíz k -ésima de un elemento de un cuerpo finito . ^{[ 8 ]}

Si se deben realizar muchas raíces cuadradas en el mismo grupo cíclico y S no es demasiado grande, se puede preparar de antemano una tabla de raíces cuadradas de los elementos de orden de potencia 2 y el algoritmo se puede simplificar y acelerar de la siguiente manera.

1. Factorizamos las potencias de 2 de p − 1, definiendo Q y S como:${\displaystyle p-1=Q2^{S}}$con Q impar.
2. Dejar${\displaystyle R\leftarrow n^{\frac {Q+1}{2}},t\leftarrow n^{Q}\equiv R^{2}/n}$
3. Encontrar${\displaystyle b}$de la tabla tal que${\displaystyle b^{2}\equiv t}$y establecer${\displaystyle R\equiv R/b}$
4. devolver R.​

• Ivan Niven ; Herbert S. Zuckerman; Hugh L. Montgomery (1991). Introducción a la teoría de los números (5.ª  ed.). Wiley. págs. 110-115 . ISBN  0-471-62546-9.
• Daniel Shanks. Cinco algoritmos de teoría de números. Actas de la Segunda Conferencia de Manitoba sobre Matemáticas Numéricas. Págs.  51–70. 1973.
• Alberto Tonelli, Bemerkung über die Auflösung quadratischer Congruenzen. Nachrichten von der Königlichen Gesellschaft der Wissenschaften und der Georg-Augusts-Universität zu Göttingen . Páginas.  344–346. 1891.
• Gagan Tara Nanda - Matemáticas 115: El algoritmo RESSOL
• Gonzalo Tornaria