El algoritmo de Tonelli-Shanks (denominado por Shanks como el algoritmo RESSOL) se utiliza en aritmética modular para resolver para r en una congruencia de la forma r 2 ≡ n (mod p ), donde p es un primo : es decir, para encontrar una raíz cuadrada de n módulo p .
Tonelli-Shanks no se puede utilizar para módulos compuestos: encontrar números compuestos de módulos de raíces cuadradas es un problema de cálculo equivalente a la factorización de enteros . [1]
Alberto Tonelli [2] [3] desarrolló una versión equivalente, pero un poco más redundante, de este algoritmo en 1891. La versión discutida aquí 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 devolvieron. [4]
Según Dickson, [3] el algoritmo de Tonelli puede tomar raíces cuadradas de las potencias p λ de módulo primo x, además de los primos.
Ideas centrales
Dado un valor distinto de cero y un primo extraño , El criterio de Euler nos dice que tiene una raíz cuadrada (es decir, es un residuo cuadrático ) si y solo si:
- .
Por el contrario, si un número no tiene raíz cuadrada (no es un residuo), el criterio de Euler nos dice que:
- .
No es dificil encontrar tal , porque la mitad de los enteros entre 1 y tiene esta propiedad. Entonces asumimos que tenemos acceso a tal no residuo.
Al dividir (normalmente) por 2 repetidamente, podemos escribir como , dónde es impar. Tenga en cuenta que si intentamos
- ,
luego . Si, luego es una raíz cuadrada de . De lo contrario, para, tenemos y satisfactorio:
- ; y
- es un -ésima raíz de 1 (porque ).
Si, dada la opción de y para un particular satisfaciendo lo anterior (donde no es una raíz cuadrada de ), podemos calcular fácilmente otro y por tal que las relaciones anteriores se mantengan, entonces podemos repetir esto hasta se convierte en un -ésima raíz de 1, es decir, . En ese punto es una raíz cuadrada de .
Podemos comprobar si es un -ésima raíz de 1 elevándola al cuadrado veces y compruebe si es 1. Si es así, entonces no necesitamos hacer nada, la misma elección de y obras. Pero si no lo es 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 ).
Para encontrar un nuevo par de y , podemos multiplicar por un factor , estar determinado. Luego debe ser multiplicado por un factor mantener . Entonces necesitamos encontrar un factor así que eso es un -ésima raíz de 1, o equivalentemente es un -ésima raíz de -1.
El truco aquí es hacer uso de , el conocido no residuo. El criterio de Euler aplicado a mostrado arriba dice que es un -ésima raíz de -1. Entonces al cuadrar repetidamente, tenemos acceso a una secuencia de -ésima raíz de -1. Podemos seleccionar el adecuado para que sirva como. Con un poco de mantenimiento de variables y compresión de casos trivial, el algoritmo siguiente surge de forma natural.
El algoritmo
Operaciones y comparaciones sobre elementos del grupo multiplicativo de enteros módulo p son implícitamente mod p .
Entradas :
- p , una prima
- n , un elemento detal que existan soluciones a la congruencia r 2 = n ; cuando esto es así, decimos que n es un residuo cuadrático mod p .
Salidas :
- r ental que r 2 = n
Algoritmo :
- Factorizando potencias de 2, encuentre Q y S tales quecon Q impar
- Buscar una z en 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 encontrando el símbolo de Jacobi.
- Dejar
- Círculo:
- Si t = 0, devuelve r = 0
- Si t = 1, devuelve r = R
- De lo contrario, use el cuadrado repetido para encontrar el mínimo i , 0 < i < M , tal que
- Dejar , y establecer
Una vez que haya resuelto la congruencia con r, la segunda solución es. Si al menos yo tal quees M , entonces no existe una 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 primos tales que p ≡ 3 (mod 4), este problema tiene posibles soluciones. Si estos satisfacen, son las únicas soluciones. Si no,, n es un no residuo cuadrático y no hay soluciones.
Prueba
Podemos mostrar que al comienzo de cada iteración del ciclo se mantienen los siguientes invariantes del ciclo :
Inicialmente:
- (dado que z es un no residuo cuadrático, según el criterio de Euler)
- (dado que n es un residuo cuadrático)
En cada iteración, con M ' , c' , t ' , R' los nuevos valores reemplazan a M , c , t , R :
- ya que tenemos eso pero ( i es el valor mínimo tal que)
De y la prueba contra t = 1 al comienzo del ciclo, vemos que siempre encontraremos una i en 0 < i < M tal que. M es estrictamente más pequeño 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 de bucle implica que R 2 = n .
Orden de t
Podemos expresar alternativamente los invariantes de bucle usando el orden de los elementos:
- como antes
Cada paso del algoritmo mueve t a un subgrupo más pequeño midiendo el orden exacto de ty multiplicándolo por un elemento del mismo orden.
Ejemplo
Resolver la congruencia r 2 ≡ 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: (como antes, operaciones en son implícitamente mod 41).
- entonces ,
- Encuentre un valor para z:
- , por lo que 2 es un residuo cuadrático según el criterio de Euler.
- , entonces 3 es un no residuo cuadrático: set
- Colocar
- Círculo:
- Primera iteración:
- , entonces no hemos terminado
- , entonces
- Segunda iteración:
- , entonces todavía no hemos terminado
- entonces
- Tercera iteración:
- y terminamos; regreso
- Primera iteración:
De hecho, 28 2 ≡ 5 (mod 41) y (−28) 2 ≡ 13 2 ≡ 5 (mod 41). Entonces, el algoritmo arroja las dos soluciones a nuestra congruencia.
Velocidad del algoritmo
El algoritmo Tonelli-Shanks requiere (en promedio sobre todas las entradas posibles (residuos cuadráticos y no residuos cuadráticos))
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 no residuo cuadrático requerido se encuentra comprobando si un número tomado al azar es un no residuo cuadrático, requiere (en promedio) cálculos del símbolo de Legendre. [5] El promedio de dos cálculos del símbolo de Legendre se explica a continuación: es un residuo cuadrático con probabilidad , que es más pequeño que pero , por lo que, en promedio, tendremos que comprobar si un es un residuo cuadrático dos veces.
Esto muestra esencialmente que el algoritmo 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 uno usa el algoritmo de Sutherland para realizar el cálculo del logaritmo discreto en el subgrupo 2-Sylow de, uno puede reemplazar con una expresión que está delimitada asintóticamente por . [6] Explícitamente, se calcula tal que y entonces satisface (tenga en cuenta que es un múltiplo de 2 porque es un residuo cuadrático).
El algoritmo requiere que encontremos un no residuo cuadrático . No existe un algoritmo determinista conocido que se ejecute en tiempo polinomial para encontrar tal. Sin embargo, si la hipótesis de Riemann generalizada es cierta, existe un no residuo cuadrático, [7] lo que permite comprobar cada hasta ese límite y encontrar un adecuado dentro del tiempo polinomial . Sin embargo, tenga en cuenta que este es el peor de los casos; en general, se encuentra en un promedio de 2 ensayos como se indicó anteriormente.
Usos
El algoritmo de Tonelli-Shanks se puede utilizar (naturalmente) para cualquier proceso en el que sean necesarias raíces cuadradas módulo a primo. Por ejemplo, se puede utilizar para encontrar puntos en curvas elípticas . También es útil para los cálculos en el criptosistema Rabin y en el paso de tamizado del tamiz cuadrático .
Generalizaciones
Tonelli-Shanks se puede generalizar a cualquier grupo cíclico (en lugar de ) y a la k- ésima raíz para un entero arbitrario k , en particular a tomar la k- ésima raíz de un elemento de un campo finito . [8]
Si se deben hacer muchas raíces cuadradas en el mismo grupo cíclico y S no es demasiado grande, se puede preparar una tabla de raíces cuadradas de los elementos de orden de 2 potencias por adelantado y el algoritmo simplificado y acelerado de la siguiente manera.
- Factoriza las potencias de 2 de p - 1, definiendo Q y S como:con Q impar.
- Dejar
- Encontrar de la mesa de tal manera que y establecer
- regresar 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]
La referencia de Dickson muestra la siguiente fórmula para la raíz cuadrada de .
- Cuándo , o (s debe ser 2 para esta ecuación) y tal que
- por luego
- dónde
- por luego
Señalando que y notando que luego
Para tomar otro ejemplo: y
Dickson también atribuye la siguiente ecuación a Tonelli:
- dónde y ;
Utilizando y usando el módulo de las matemáticas siguen:
Primero, encuentre el mod de raíz cuadrada modular que se puede hacer mediante el algoritmo regular de Tonelli:
- y por lo tanto
Y aplicando la ecuación de Tonelli (ver arriba):
La referencia de Dickson [3] muestra claramente que el algoritmo de Tonelli funciona en módulos de.
Notas
- ^ Oded Goldreich, Complejidad computacional: una perspectiva conceptual , Cambridge University Press, 2008, p. 588.
- ^ 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.
- ^ a b c d e Leonard Eugene Dickson (1919). Historia de la Teoría de los Números . 1 . págs. 215 –216.
- ^ Daniel Shanks. Cinco algoritmos teóricos de números. Actas de la Segunda Conferencia de Manitoba sobre Matemáticas Numéricas. Páginas. 51–70. 1973.
- ^ Gonzalo Tornaria - Raíces cuadradas módulo p, página 2 https://doi.org/10.1007%2F3-540-45995-2_38
- ^ Sutherland, Andrew V. (2011), " Cálculo de estructuras y logaritmos discretos en grupos p abelianos finitos", Mathematics of Computation , 80 : 477–500, arXiv : 0809.3413 , doi : 10.1090 / s0025-5718-10-02356-2
- ^ Bach, Eric (1990), "Límites explícitos para pruebas de primalidad y problemas relacionados", Matemáticas de Computación , 55 (191): 355–380, doi : 10.2307 / 2008811 , JSTOR 2008811
- ^ Adleman, LM, K. Manders y G. Miller: 1977, "Sobre echar raíces en campos finitos". En: 18º Simposio IEEE sobre Fundamentos de las Ciencias de la Computación. págs. 175-177
- ^ "Accademia nazionale dei Lincei, Roma. Rendiconti, (5), 1, 1892, 116-120".
Referencias
- 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. Algoritmos teóricos de cinco números. Actas de la Segunda Conferencia de Manitoba sobre Matemáticas Numéricas. Páginas. 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]