En teoría computacional de números , el algoritmo de Cipolla es una técnica para resolver una congruencia de la forma
dónde , entonces n es el cuadrado de x , y dondees un primo extraño . Aquídenota el campo finito con elementos ;. El algoritmo lleva el nombre de Michele Cipolla , un matemático italiano que lo descubrió en 1907.
Además de los módulos primos, el algoritmo de Cipolla también puede tomar potencias de módulo primo de raíces cuadradas. [1]
Algoritmo
Entradas:
- , un primo impar,
- , que es un cuadrado.
Salidas:
- , satisfactorio
El paso 1 es encontrar un tal que no es un cuadrado. No existe un algoritmo conocido para encontrar tal, excepto el método de prueba y error . Simplemente elija uny calculando el símbolo de Legendre uno puede ver si satisface la condición. La posibilidad de que un azar satisfará es . Con lo suficientemente grande esto es sobre . [2] Por lo tanto, el número esperado de ensayos antes de encontrar un es aproximadamente 2.
El paso 2 es calcular x calculando dentro del campo . Esta x será la que satisfaga
Si , luego también sostiene. Y como p es impar,. Entonces, siempre que se encuentra una solución x , siempre hay una segunda solución, -x .
Ejemplo
(Nota: Todos los elementos antes del paso dos se consideran un elemento de y todos los elementos del paso dos se consideran elementos de ).
Encuentra todo x tal que
Antes de aplicar el algoritmo, se debe comprobar que es de hecho un cuadrado en . Por tanto, el símbolo de Legendretiene que ser igual a 1. Esto se puede calcular utilizando el criterio de Euler ; Esto confirma que 10 es un cuadrado y, por lo tanto, se puede aplicar el algoritmo.
- Paso 1: Encontrar un un tal queno es un cuadrado. Como se dijo, esto debe hacerse mediante prueba y error. Escoger. Luego se convierte en 7. El símbolo de Legendre tiene que ser -1. Nuevamente, esto se puede calcular utilizando el criterio de Euler. Entonces es una opción adecuada para a .
- Paso 2: Calcular
Entonces es una solución, así como En efecto, y
Prueba
La primera parte de la prueba es verificar que es de hecho un campo. En aras de la simplicidad de la notación, Se define como . Por supuesto,es un no residuo cuadrático, por lo que no hay raíz cuadrada en. Estopuede verse aproximadamente como análogo al número complejo i . La aritmética de campo es bastante obvia. La adición se define como
- .
La multiplicación también se define como de costumbre. Teniendo en cuenta que, se vuelve
- .
Ahora hay que comprobar las propiedades del campo. Las propiedades de cierre bajo suma y multiplicación, asociatividad , conmutatividad y distributividad se ven fácilmente. Esto se debe a que en este caso el campose parece un poco al campo de los números complejos (consiendo el análogo de i ).
La identidad aditiva es, o más formalmente : Dejar , luego
- .
La identidad multiplicativa es , o más formalmente :
- .
Lo único que queda para ser un campo es la existencia de inversos aditivos y multiplicativos . Se ve fácilmente que el aditivo inverso de es , que es un elemento de , porque . De hecho, estos son los elementos inverso aditivo de x y y . Por demostrar que cada elemento distinto de cero tiene un inverso multiplicativo, escribe y . En otras palabras,
- .
Entonces las dos igualdades y debe aguantar. Resolver los detalles da expresiones para y , a saber
- ,
- .
Los elementos inversos que se muestran en las expresiones de y existen, porque todos estos son elementos de . Esto completa la primera parte de la demostración, mostrando que es un campo.
La segunda y media parte de la demostración muestra que para cada elemento . Por definición, no es un cuadrado en . El criterio de Euler dice entonces que
- .
Por lo tanto . Esto, junto con el pequeño teorema de Fermat (que dice que para todos ) y el conocimiento de que en campos de característica p la ecuaciónsostiene, una relación a veces llamada el sueño de Freshman , muestra el resultado deseado
- .
La tercera y última parte de la prueba es mostrar que si , luego .
Calcular
- .
Tenga en cuenta que este cálculo se llevó a cabo en , así que esto . Pero con el teorema de Lagrange , afirmando que un polinomio distinto de cero de grado n tiene como máximo n raíces en cualquier campo K , y el conocimiento de que tiene 2 raíces en , estas raíces deben ser todas las raíces en . Se acaba de demostrar que y son raíces de en , entonces debe ser que . [3]
Velocidad
Después de encontrar un adecuado una , el número de operaciones necesarias para el algoritmo es multiplicaciones, sumas, donde m es el número de dígitos en la representación binaria de p y k es el número de unos en esta representación. Para encontrar un por ensayo y error, el número esperado de cálculos del símbolo de Legendre es 2. Pero uno puede tener suerte con el primer intento y es posible que necesite más de 2 intentos. En el campo, las siguientes dos igualdades se mantienen
dónde se conoce de antemano. Este cálculo necesita 4 multiplicaciones y 4 sumas.
dónde y . Esta operación necesita 6 multiplicaciones y 4 sumas.
Asumiendo que (en el caso , el cálculo directo es mucho más rápido) la expresión binaria de posee dígitos, de los cuales k son unos. Entonces, para calcular un el poder de , se debe utilizar la primera fórmula veces y el segundo veces.
Para esto, el algoritmo de Cipolla es mejor que el algoritmo Tonelli-Shanks si y solo si, con siendo la potencia máxima de 2 que divide . [4]
Módulos de potencia primarios
Según la "Historia de los números" de Dickson, la siguiente fórmula de Cipolla encontrará raíces cuadradas módulo potencias de primos: [5] [6]
- dónde y
- dónde , como en el ejemplo de este artículo
Tomando el ejemplo del artículo de wiki, podemos ver que esta fórmula anterior de hecho toma poderes de módulo primo de raíces cuadradas.
Como
Ahora resuelve para vía:
Ahora crea el y (Vea aquí el código de mathica que muestra este cálculo anterior, recordando que algo cercano a la aritmética modular compleja está sucediendo aquí)
Como tal:
- y
y la ecuación final es:
- cual es la respuesta.
Referencias
- ^ "Historia de la teoría de los números" Volumen 1 por Leonard Eugene Dickson, p218 leer en línea
- ^ R. Crandall, C. Números primos de Pomerance: Una perspectiva computacional Springer-Verlag, (2001) p. 157
- ^ Algoritmo de M. Baker Cipolla para encontrar raíces cuadradas mod p
- ^ Gonzalo Tornaria Raíces cuadradas módulo p
- ^ "Historia de la teoría de los números" Volumen 1 por Leonard Eugene Dickson, p218, Chelsea Publishing 1952 leído en línea
- ^ Michelle Cipolla, Rendiconto dell 'Accademia delle Scienze Fisiche e Matematiche. Nápoles, (3), 10.1904, 144-150
Fuentes
- E. Bach, JO Shallit Teoría algorítmica de números: algoritmos eficientes MIT Press, (1996)
- Leonard Eugene Dickson Historia de la teoría de los números Volumen 1 p218 [1]
- ^ "Historia de la teoría de los números" Volumen 1 por Leonard Eugene Dickson, p218, Chelsea Publishing 1952 url = https://archive.org/details/historyoftheoryo01dick