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}$ is not particularly large with respect to the number of digits in the binary representation of ${\displaystyle p}$. As written above, Cipolla's algorithm works better than Tonelli–Shanks if (and only if) ${\displaystyle S(S-1)>8m+20}$. However, if one instead uses Sutherland's algorithm to perform the discrete logarithm computation in the 2-Sylow subgroup of ${\displaystyle \mathbb {F} _{p}^{\ast }}$, one may replace ${\displaystyle S(S-1)}$ with an expression that is asymptotically bounded by ${\displaystyle O(S\log S/\log \log S)}$.^[6] Explicitly, one computes ${\displaystyle e}$ such that ${\displaystyle c^{e}\equiv n^{Q}}$ and then ${\displaystyle R\equiv c^{-e/2}n^{(Q+1)/2}}$ satisfies ${\displaystyle R^{2}\equiv n}$ (note that ${\displaystyle e}$ is a multiple of 2 because ${\displaystyle n}$ is a quadratic residue).

The algorithm requires us to find a quadratic nonresidue ${\displaystyle z}$. There is no known deterministic algorithm that runs in polynomial time for finding such a ${\displaystyle z}$. However, if the generalized Riemann hypothesis is true, there exists a quadratic nonresidue ${\displaystyle z<2\ln ^{2}{p}}$,^[7] making it possible to check every ${\displaystyle z}$ up to that limit and find a suitable ${\displaystyle z}$ within polynomial time. Keep in mind, however, that this is a worst-case scenario; in general, ${\displaystyle z}$ is found in on average 2 trials as stated above.

The Tonelli–Shanks algorithm can (naturally) be used for any process in which square roots modulo a prime are necessary. For example, it can be used for finding points on elliptic curves. It is also useful for the computations in the Rabin signature algorithm and in the sieving step of the quadratic sieve.

Tonelli–Shanks can be generalized to any cyclic group (instead of ${\displaystyle (\mathbb {Z} /p\mathbb {Z} )^{\times }}$) and to kth roots for arbitrary integer k, in particular to taking the kth root of an element of a finite field.^[8]

If many square-roots must be done in the same cyclic group and S is not too large, a table of square-roots of the elements of 2-power order can be prepared in advance and the algorithm simplified and sped up as follows.

1. Factor out powers of 2 from p − 1, defining Q and S as: ${\displaystyle p-1=Q2^{S}}$ with Q odd.
2. Let ${\displaystyle R\leftarrow n^{\frac {Q+1}{2}},t\leftarrow n^{Q}\equiv R^{2}/n}$
3. Find ${\displaystyle b}$ from the table such that ${\displaystyle b^{2}\equiv t}$ and set ${\displaystyle R\equiv R/b}$
4. return 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