Algoritmo de Tonelli-Shanks

El algoritmo Tonelli-Shanks (al que Shanks denomina 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 método 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, pero ligeramente más redundante, de este algoritmo. La versión que aquí se analiza fue desarrollada independientemente por Daniel Shanks en 1973, quien explicó:

Mi tardanza en conocer estas referencias históricas se debió a que le había prestado 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 primos.

Ideas centrales

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

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

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

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

No es difícil encontrar tal , porque la mitad de los números enteros entre 1 y tienen esta propiedad. Por lo tanto, suponemos que tenemos acceso a dicho residuo no válido. ${\displaystyle z}$ ${\displaystyle p-1}$

Al dividir (normalmente) por 2 repetidamente, podemos escribir como , donde es impar. Tenga en cuenta que si intentamos ${\displaystyle p-1}$ ${\displaystyle Q2^{S}}$ ${\displaystyle Q}$

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

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

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

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

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

Para encontrar un nuevo par de y , podemos multiplicar por un factor , que se determinará. Luego, se debe multiplicar por un factor para mantener . Por lo tanto, cuando es -1, debemos encontrar un factor que sea una raíz -ésima de 1, o equivalentemente, sea una raíz -ésima de -1. ${\displaystyle R}$ ${\displaystyle t}$ ${\displaystyle R}$ ${\displaystyle b}$ ${\displaystyle t}$ ${\displaystyle b^{2}}$ ${\displaystyle R^{2}\equiv nt{\pmod {p}}}$ ${\displaystyle t^{2^{M-2}}}$ ${\displaystyle b^{2}}$ ${\displaystyle tb^{2}}$ ${\displaystyle 2^{M-2}}$ ${\displaystyle b^{2}}$ ${\displaystyle 2^{M-2}}$

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

El algoritmo

Las operaciones y comparaciones sobre elementos del grupo multiplicativo de números enteros módulo p son implícitamente mod p . ${\displaystyle \mathbb {Z} /p\mathbb {Z} }$

Entradas :

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

Salidas :

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

Algoritmo :

1. Al factorizar potencias de 2, encuentre Q y S tales que con Q impar ${\displaystyle p-1=Q2^{S}}$
2. Búsqueda de una z en la que haya un residuo cuadrático no válido ${\displaystyle \mathbb {Z} /p\mathbb {Z} }$
   • La mitad de los elementos del conjunto serán residuos no cuadráticos.
   • Los candidatos pueden probarse con el criterio de Euler o encontrando el 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 el cuadrado repetido para encontrar el menor i , 0 < i < M , tal que ${\displaystyle t^{2^{i}}=1}$
   • Sea , y establezca ${\displaystyle b\leftarrow c^{2^{M-i-1}}}$

     ${\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 . Si el menor i tal que es M , entonces no existe solución para la congruencia, es decir, n no es un residuo cuadrático. ${\displaystyle -r{\pmod {p}}}$ ${\displaystyle t^{2^{i}}=1}$

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

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

Prueba

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

• ${\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 residuo cuadrático no residual, 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 reemplazan 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 pero ( i es el menor valor tal que ) ${\displaystyle t^{2^{i}}=1}$ ${\displaystyle t^{2^{i-1}}\neq 1}$ ${\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}$

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

Orden dea

Podemos expresar alternativamente los invariantes del bucle utilizando el orden de los elementos:

• ${\displaystyle \operatorname {ord} (c)=2^{M}}$
• ${\displaystyle \operatorname {ord} (t)|2^{M-1}}$
• ${\displaystyle R^{2}=tn}$como antes

Cada paso del algoritmo mueve t a un subgrupo más pequeño midiendo el orden exacto de t y multiplicándolo por un elemento del mismo orden.

Ejemplo

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

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 que 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}$, entonces ${\displaystyle t^{2^{2}}=1}$ ${\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; volvamos ${\displaystyle r=R=28}$

De hecho, 28 ² ≡ 5 (mod 41) y (−28) ² ≡ 13 ² ≡ 5 (mod 41). Por lo tanto, el algoritmo arroja las dos soluciones de nuestra congruencia.

Velocidad del algoritmo

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 es el número de dígitos en la representación binaria de y es el número de unos en la representación binaria de . Si el residuo cuadrático no requerido se debe encontrar comprobando si un número tomado al azar es un residuo cuadrático no, requiere (en promedio) 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: es un residuo cuadrático con probabilidad , que es menor que pero , por lo que en promedio necesitaremos comprobar si a es un residuo cuadrático dos veces. ${\displaystyle m}$ ${\displaystyle p}$ ${\displaystyle k}$ ${\displaystyle p}$ ${\displaystyle z}$ ${\displaystyle y}$ ${\displaystyle 2}$ ${\displaystyle y}$ ${\displaystyle {\tfrac {\tfrac {p+1}{2}}{p}}={\tfrac {1+{\tfrac {1}{p}}}{2}}}$ ${\displaystyle 1}$ ${\displaystyle \geq {\tfrac {1}{2}}}$ ${\displaystyle y}$

Esto demuestra esencialmente que el algoritmo de Tonelli-Shanks funciona muy bien si el módulo es aleatorio, es decir, si no es particularmente grande con respecto al número de dígitos en la representación binaria de . Como se escribió anteriormente, el algoritmo de Cipolla funciona mejor que Tonelli-Shanks si (y solo si) . 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 , se puede reemplazar con una expresión que esté asintóticamente limitada por . ^[6] Explícitamente, se calcula de modo que y luego satisface (nótese que es un múltiplo de 2 porque es un residuo cuadrático). ${\displaystyle p}$ ${\displaystyle S}$ ${\displaystyle p}$ ${\displaystyle S(S-1)>8m+20}$ ${\displaystyle \mathbb {F} _{p}^{\ast }}$ ${\displaystyle S(S-1)}$ ${\displaystyle O(S\log S/\log \log S)}$ ${\displaystyle e}$ ${\displaystyle c^{e}\equiv n^{Q}}$ ${\displaystyle R\equiv c^{-e/2}n^{(Q+1)/2}}$ ${\displaystyle R^{2}\equiv n}$ ${\displaystyle e}$ ${\displaystyle n}$

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

Usos

El algoritmo de Tonelli-Shanks puede utilizarse (naturalmente) para cualquier proceso en el que sean necesarias raíces cuadradas módulo primo. Por ejemplo, puede utilizarse para encontrar puntos en curvas elípticas . También es útil para los cálculos en el criptosistema de Rabin y en el paso de cribado del tamiz cuadrático .

Generalizaciones

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

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 2-potencia y simplificar y acelerar el algoritmo de la siguiente manera.

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

El algoritmo de Tonelli funcionará en mod p^k

Según la "Teoría de los números" de Dickson ^[3]

A. Tonelli ^[9] dio una fórmula explícita para las raíces de ^[3] ${\displaystyle x^{2}=c{\pmod {p^{\lambda }}}}$

La referencia de Dickson muestra la siguiente fórmula para la raíz cuadrada de . ${\displaystyle x^{2}{\bmod {p^{\lambda }}}}$

cuando , o (s debe ser 2 para esta ecuación) y tal que ${\displaystyle p=4\cdot 7+1}$ ${\displaystyle s=2}$ ${\displaystyle A=7}$ ${\displaystyle 29=2^{2}\cdot 7+1}$

Para entonces ${\displaystyle x^{2}{\bmod {p^{\lambda }}}\equiv c}$

${\displaystyle x{\bmod {p^{\lambda }}}\equiv \pm (c^{A}+3)^{\beta }\cdot c^{(\beta +1)/2}}$dónde ${\displaystyle \beta \equiv a\cdot p^{\lambda -1}}$

Tomando nota de eso y tomando nota de eso entonces ${\displaystyle 23^{2}{\bmod {29^{3}}}\equiv 529}$ ${\displaystyle \beta =7\cdot 29^{2}}$

${\displaystyle (529^{7}+3)^{7\cdot 29^{2}}\cdot 529^{(7\cdot 29^{2}+1)/2}{\bmod {29^{3}}}\equiv 24366\equiv -23}$

Para tomar otro ejemplo: y ${\displaystyle 2333^{2}{\bmod {29^{3}}}\equiv 4142}$

${\displaystyle (4142^{7}+3)^{7\cdot 29^{2}}\cdot 4142^{(7\cdot 29^{2}+1)/2}{\bmod {29^{3}}}\equiv 2333}$

Dickson también atribuye la siguiente ecuación a Tonelli:

${\displaystyle X{\bmod {p^{\lambda }}}\equiv x^{p^{\lambda -1}}\cdot c^{(p^{\lambda }-2p^{\lambda -1}+1)/2}}$donde y ; ${\displaystyle X^{2}{\bmod {p^{\lambda }}}\equiv c}$ ${\displaystyle x^{2}{\bmod {p}}\equiv c}$

Usando y empleando el módulo de la matemática se sigue: ${\displaystyle p=23}$ ${\displaystyle p^{3}}$

${\displaystyle 1115^{2}{\bmod {23^{3}}}=2191}$

Primero, encuentre la raíz cuadrada modular mod , lo que se puede hacer mediante el algoritmo de Tonelli regular: ${\displaystyle p}$

${\displaystyle 1115^{2}{\bmod {23}}\equiv 6}$y por lo tanto ${\displaystyle {\sqrt {6}}{\bmod {23}}\equiv 11}$

Y aplicando la ecuación de Tonelli (ver arriba):

${\displaystyle 11^{23^{2}}\cdot 2191^{(23^{3}-2\cdot 23^{2}+1)/2}{\bmod {23^{3}}}\equiv 1115}$

La referencia de Dickson ^[3] muestra claramente que el algoritmo de Tonelli funciona con módulos de . ${\displaystyle p^{\lambda }}$

Notas

1. Oded Goldreich, Complejidad computacional: una perspectiva conceptual , Cambridge University Press, 2008, pág. 588.
2. Volker Diekert; Manfred Kufleitner; Gerhard Rosenberger; Ulrich Hertrampf (24 de mayo de 2016). Métodos algebraicos discretos: aritmética, criptografía, autómatas y grupos. De Gruyter. págs. 163-165. ISBN 978-3-11-041632-9.
3. Leonard Eugene Dickson (1919). Historia de la teoría de los números. Vol. 1. Washington, Carnegie Institution of Washington. págs. 215–216.
4. 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.
5. Gonzalo Tornaria - Raíces cuadradas módulo p, página 2 https://doi.org/10.1007%2F3-540-45995-2_38
6. Sutherland, Andrew V. (2011), "Cálculo de estructuras y logaritmos discretos en p-grupos abelianos finitos", Matemáticas de la computación , 80 (273): 477–500, arXiv : 0809.3413 , doi :10.1090/s0025-5718-10-02356-2, S2CID  13940949
7. Bach, Eric (1990), "Límites explícitos para pruebas de primalidad y problemas relacionados", Mathematics of Computation , 55 (191): 355–380, doi : 10.2307/2008811 , JSTOR  2008811
8. Adleman, LM, K. Manders y G. Miller: 1977, «Sobre la toma de raíces en campos finitos». En: 18.º Simposio IEEE sobre Fundamentos de la Ciencia de la Computación, págs. 175-177
9. "Accademia nazionale dei Lincei, Roma. Rediconti, (5), 1, 1892, 116-120".

Referencias

• Ivan Niven; Herbert S. Zuckerman; Hugh L. Montgomery (1991). Introducción a la teoría de números (quinta edición). Wiley. Págs. 110-115. ISBN 0-471-62546-9.
• Daniel Shanks. Cinco algoritmos teóricos 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. [1]
• Gagan Tara Nanda - Matemáticas 115: El algoritmo RESSOL [2]
• Gonzalo Tornaria [3]