Algoritmo de Tonelli-Shanks

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 7 de marzo de 2020; la verificación requiere 1 edición .

El algoritmo Tonelli-Shanks (llamado algoritmo RESSOL por Shanks) pertenece a la aritmética modular y se utiliza para resolver comparaciones

x^{2}\equiv n{\pmod {p)),

donde es el módulo del residuo cuadrático , y es un número primo impar . $norte$ $pags$ $pags$

El algoritmo Tonelli-Shanks no se puede utilizar para módulos compuestos; la búsqueda de raíces cuadradas módulo compuesto es computacionalmente equivalente a la factorización [1] .

Una versión equivalente pero un poco más complicada de este algoritmo fue desarrollada por Alberto Tonelli en 1891. La versión del algoritmo discutida aquí fue desarrollada de forma independiente por Daniel Shanks en 1973.

Algoritmo

Datos de entrada : — un número primo impar, — un número entero que es un módulo de residuo cuadrático , en otras palabras , donde está el símbolo de Legendre . $pags$ $norte$ $pags$ $\left({\frac {n}{p}}\right)=1$ $\left(\frac{a}{b}\right)$

El resultado del algoritmo : un residuo que satisface la comparación . $R$ $R^{2}\equiv n{\pmod {p}}$

Seleccionamos potencias de dos de , es decir, sea , donde impar, . Tenga en cuenta que si , es decir , la solución está determinada por la fórmula . A continuación, suponemos . $p-1$ $p-1=2^{S}Q$ $q$ ${\ Displaystyle S \ geqslant 1}$ ${\ estilo de visualización S = 1}$ $p \equiv 3 \pmod 4$ $R\equiv \pm n^{\frac {p+1}{4))$ ${\ Displaystyle S \ geqslant 2}$
Elegimos un no residuo cuadrático arbitrario , es decir, el símbolo de Legendre , y establecemos . $z$ $\left({\frac {z}{p}}\right)=-1$ $c\equiv z^{Q}{\pmod {p))$
Deja también $R\equiv n^{\frac {Q+1}{2}}{\pmod {p)),$ $t\equiv n^{Q}{\pmod {p)),$ ${\ estilo de visualización M = S.}$
Ejecutamos el ciclo:
1. Si , entonces el algoritmo devuelve . $t\equiv 1{\pmod {p}}$ $R$
2. De lo contrario, en el bucle encontramos el más pequeño , , tal que iterando al cuadrado. $i$ ${\ estilo de visualización 0 <i <M}$ $t^{2^{i}}\equiv 1{\pmod {p}}$
3. Let , y let , volver al comienzo del ciclo. $b\equiv c^{2^{Mi-1}}{\pmod {p}}$ $R:\equiv Rb{\pmod {p)),$ $t:\equiv tb^{2}{\pmod {p)),$ $c:\equiv b^{2}{\pmod {p)),$ ${\ estilo de visualización M: = i}$

Después de encontrar la solución de comparación, la segunda solución de comparación se encuentra como . $R$ $PR$

Ejemplo

Hagamos una comparación . es impar, y como , 10 es un residuo cuadrático según el criterio de Euler . $x^{2}\equiv 10{\pmod {13}}$ ${\ estilo de visualización p = 13}$ $10^{\frac {13-1}{2}}=10^{6}\equiv 1{\pmod {13}}$

Paso 1: entonces , . ${\displaystyle p-1=12=3\cdot 2^{2))$ ${\ estilo de visualización Q = 3}$ ${\ estilo de visualización S = 2}$
Paso 2: Tomar - no residuo cuadrático (porque (nuevamente por el criterio de Euler)). Pongamos ${\ estilo de visualización z = 2}$ $2^{\frac {13-1}{2}}=-1{\pmod {13}}$ $c=2^{3}\equiv 8{\pmod {13)).$
Paso 3: $R=10^{2}\equiv -4,\;t\equiv 10^{3}\equiv -1{\pmod {13)),M=2.$
Paso 4: Comience el bucle: entonces , para decirlo de manera simple, . $t\not \equiv 1{\pmod {13}}$ ${\ estilo de visualización 0 <i <2}$ ${\ estilo de visualización i = 1}$
- Deja , entonces . $b\equiv 8^{2^{2-1-1}}\equiv 8{\pmod {13}}$ $b^{2}\equiv 8^{2}\equiv -1{\pmod {13}}$
- Pongamos , , y . $R=-4\cdot 8\equiv 7{\pmod {13}}$ $t\equiv -1\cdot -1\equiv 1{\pmod {13))$ ${\ estilo de visualización M = 1}$
- Reinicie el ciclo, ya que el ciclo está completo, obtenemos $t\equiv 1{\pmod {13}}$ $R\equiv 7{\pmod {13)).$

Dado que , obviamente , de aquí obtenemos 2 soluciones de comparación. $7^{2}=49\equiv 10{\pmod {13}}$ $(\pm 7)^{2}\equiv 6^{2}\equiv 10{\pmod {13))$

Prueba

deja _ Vamos ahora y , tenga en cuenta que . La última comparación sigue siendo cierta después de cada iteración del bucle principal del algoritmo. Si en algún momento , el algoritmo termina con . $p-1=2^{S}Q$ $r\equiv n^{\frac {Q+1}{2}}{\pmod {p}}$ $t\equiv n^{Q}{\pmod {p}}$ $r^{2}\equiv nt{\pmod {p}}$ $t\equiv 1{\pmod {p}}$ $r^{2}\equiv n{\pmod {p}}$ $R\equiv \pm r{\pmod {p}}$

Si , entonces considere el módulo cuadrático sin residuos . Sea , entonces y , lo que demuestra que el orden es . $t\not \equiv 1{\pmod {p}}$ $z$ $pags$ $c\equiv z^{Q}{\pmod {p))$ $c^{2^{S}}\equiv (z^{Q})^{2^{S}}\equiv z^{p-1}\equiv 1{\pmod {p}}$ $c^{2^{S-1}}\equiv z^{\frac {p-1}{2}}\equiv \left({\frac {z}{p}}\right)\equiv -1{\pmod {p}}$ $C$ ${\ estilo de visualización 2^{S}}$

De manera similar, obtenemos que , por lo que el orden divide a , por lo que el orden es . Dado que es un módulo cuadrado , entonces también es un cuadrado, lo que significa que . $t^{2^{S}}\equiv 1{\pmod {p}}$ $t$ ${\ estilo de visualización 2^{S}}$ $t$ ${\ estilo de visualización 2^{S'}}$ $norte$ $pags$ $t\equiv n^{Q}{\pmod {p}}$ ${\ estilo de visualización S'<S}$

Supongamos que y , y . Como antes, se conserva; sin embargo, en esta construcción , ambos y tienen orden . De ello se deduce que tiene el orden , donde . $b\equiv c^{2^{SS'-1}}{\pmod {p}}$ $r'\equiv br{\pmod {p}}$ $c'\equiv b^{2}{\pmod {p))$ $t'\equiv c't{\pmod {p}}$ $r'^{2}\equiv nt'{\pmod {p}}$ $t$ ${\ estilo de visualización c'}$ ${\ estilo de visualización 2^{S'}}$ $t'$ ${\ estilo de visualización 2^{S''}}$ ${\ estilo de visualización S''<S'}$

Si , entonces , y el algoritmo se detiene, regresando . De lo contrario, reiniciamos el bucle con definiciones similares hasta que obtenemos , que es igual a 0. Dado que la secuencia de naturales es estrictamente decreciente, el algoritmo termina. ${\ estilo de visualización S''=0}$ $t'\equiv 1{\pmod {p}}$ $R\equiv \pm r'{\pmod {p}}$ ${\ estilo de visualización b',r'',c'',t''}$ $S^{(j)'}$ $S^{(j)'}$

Velocidad del algoritmo

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

2m+2k+{\frac {S(S-1)}{4}}+{\frac {1}{2^{S-1}}}-9=O(S^{2})= O(\ln^{2}p)

módulo de multiplicaciones, donde es el número de dígitos en la representación binaria , y es el número de unos en la representación binaria . Si el no residuo cuadrático requerido se calcula comprobando uno elegido al azar para saber si es un no residuo cuadrático, entonces, en promedio, esto requiere calcular dos símbolos de Legendre [2] . Dos como el número promedio de símbolos de Legendre calculados se explica de la siguiente manera: la probabilidad de que sea un residuo cuadrático es : la probabilidad es mayor a la mitad, por lo que en promedio tomará alrededor de dos comprobaciones si es un residuo cuadrático. $m=\lceil \log _{2}p\rceil =O(\ln p)$ $pags$ $k$ $pags$ $z$ $y$ $y$ ${\frac {\frac {p+1}{2}}{p}}={\frac {1}{2}}+{\frac {1}{2p}}>{\frac {1 {2}}$ $y$

Esto demuestra que, en la práctica, el algoritmo de Tonelli-Shanks funcionará muy bien si el módulo es aleatorio, es decir, cuando no es particularmente grande en relación con el número de dígitos en la representación binaria . El algoritmo de Cipolla funciona mejor que el algoritmo de Tonelli-Shanks si y solo si . Sin embargo, si en su lugar se usa el algoritmo de Sutherland para realizar el logaritmo discreto en el subgrupo 2- Sylow de , esto permite que el número de multiplicaciones en la expresión sea reemplazado por un valor acotado asintóticamente [3] . De hecho, basta con encontrar uno que satisfaga incluso entonces (nótese que es un múltiplo de 2, ya que es un residuo cuadrático). $pags$ $S$ $pags$ $S(S-1)>8m+20$ $\mathbb {F} _{p}$ ${\ estilo de visualización S (S-1)}$ $O\left({\frac {S\ln S}{\ln \ln S}}\right)$ $mi$ ${\displaystyle c^{e}\equiv n^{Q))$ ${\displaystyle R\equiv c^{-e/2}n^{(Q+1)/2))$ $R^{2}\equivn$ $mi$ $norte$

El algoritmo requiere encontrar un no residuo cuadrático . Por el momento, no existe un algoritmo determinista , que encontraría tal , en tiempo polinomial de longitud . Sin embargo, si la hipótesis de Riemann generalizada es verdadera, entonces hay un no residuo cuadrático , [4] , que es fácil de encontrar verificando dentro de los límites especificados en tiempo polinomial . Esta es, por supuesto, una estimación del peor de los casos, ya que, como se muestra arriba, basta con verificar en promedio 2 aleatorios para encontrar un no residuo cuadrático. $z$ $pags$ $z$ ${\ estilo de visualización z <2 \ ln ^ {2} {p}}$ $z$ $z$

Aplicación

El algoritmo de Tonelli-Shanks se puede utilizar para encontrar puntos en una curva elíptica sobre un campo de residuos . También se puede utilizar para cálculos en el criptosistema Rabin .

Generalización

El algoritmo de Tonelli-Shanks se puede generalizar a cualquier grupo cíclico (en lugar de ) ya encontrar raíces de grado ésimo para un natural arbitrario , en particular, a calcular las raíces de grado ésimo en un campo finito [5] . ${\ estilo de visualización \ mathbb {F} _ {p}^ {\ veces}}$ $k$ $k$ $k$

Si hay muchas raíces cuadradas a calcular en un mismo grupo cíclico y no muy grandes, para mejorar y simplificar el algoritmo y aumentar su velocidad, se puede preparar una tabla de raíces cuadradas de los cuadrados de los elementos de la siguiente manera: $S$

Destacamos potencias de dos en : sea tal que , sea impar. $p-1$ ${\ estilo de visualización Q, S}$ $p-1=2^{S}Q$ $q$
deja _ $R\equiv n^{\frac {Q+1}{2)){\pmod {p)),t\equiv n^{Q}\equiv R^{2}/n{\pmod {p }}$
Encontremos la raíz de la tabla de razones y pongamos $b$ $b^{2}\equiv t$ $R\equiv R/b$
Volver _ $R$

Notas

↑ Oded Goldreich, Complejidad computacional: una perspectiva conceptual , Cambridge University Press, 2008, p. 588.
↑ Gonzalo Tornaria , Raíces cuadradas módulo p (enlace no disponible) , página 2.
↑ Sutherland, Andrew V. (2011), Computación de estructura y logaritmos discretos en grupos p abelianos finitos , Matemáticas de computación Vol. 80: 477–500 , DOI 10.1090/s0025-5718-10-02356-2
↑ Bach, Eric (1990), Límites explícitos para las pruebas de primalidad y problemas relacionados , Matemáticas de computación Vol. 55 (191): 355–380 , DOI 10.2307/2008811
↑ LM Adleman, K. Manders, G. Miller: 1977, "Sobre echar raíces en campos finitos". En: 18º Simposio IEEE sobre Fundamentos de Ciencias de la Computación. pags. 175–177.

Literatura

Nesterenko A. Yu. Métodos teóricos de números en criptografía. - Moscú. - 2012. - ISBN 978-5-94506-320-4 .
Ishmukhametov Sh. T. Métodos de factorización para números naturales. — Universidad de Kazán. — 2011.
Ivan Niven, Herbert S. Zuckerman, Hugh L. Montgomery . Introducción a la teoría de los números. — 5to. - Wiley, 1991. - ISBN 0-471-62546-9 .
Daniel Shank. Algoritmos teóricos de cinco números. Actas de la Segunda Conferencia de Manitoba sobre Matemáticas Numéricas. págs. 51–70. 1973.
Alberto Tonelli, Bemerkung uber die Auflosung quadratischer Congruenzen . Nachrichten von der Koniglichen Gesellschaft der Wissenschaften und der Georg-Augusts-Universitat zu Gottingen. págs. 344-346. 1891.
Gagan Tara Nanda - Matemáticas 115: El Algoritmo RESSOL .

Enlaces

Implementación de Python http://eli.thegreenplace.net/2009/03/07/computing-modular-square-roots-in-python

Algoritmos de teoría de números
Pruebas de simplicidad	Molinero Miller - Rabín Luca-Lemaire pepina Agrawala - Kayala - Sajonia Ruiseñor - Strassen
Encontrar números primos	Iterando sobre divisores Tamiz de Eratóstenes tamiz de atkin Tamiz Sundarama
Factorización	Iterando sobre divisores método Fermat p −1 Método de Pollard Algoritmo ρ de Pollard método Lehmann Método de la curva elíptica (algoritmo de Lenstra) algoritmo de dixon tamiz cuadrado
logaritmo discreto	Algoritmo de Gelfond-Shanks Algoritmo de Polig-Hellman Método ρ de Pollard Algoritmo del canguro de Pollard algoritmo de Adleman algoritmo COS
Encontrar MCD	Algoritmo de Euclides Algoritmo avanzado Algoritmo binario
Módulo aritmético	algoritmo de Montgomery Teorema del resto chino
Multiplicación y división de números.	Algoritmo Karatsuba Algoritmo de Toom-Cook Algoritmo de Schönhage-Strassen Algoritmo del Führer Algoritmo de Harvey-van der Hoeven Algoritmo de Burnickel-Ziegler
Calcular la raíz cuadrada	Algoritmo de Tonelli-Shanks Algoritmo de Berlekamp-Rabin