El algoritmo de Cipolla

En la teoría computacional de números , el algoritmo de Cipolla es una técnica para resolver una congruencia de la forma

${\displaystyle x^{2}\equiv n{\pmod {p}},}$

dónde${\displaystyle x,n\in \mathbf {F} _{p}}$, entonces n es el cuadrado de x , y donde${\displaystyle p}$es un primo impar . Aquí${\displaystyle \mathbf {F} _{p}}$denota el campo finito con${\displaystyle p}$elementos ;${\displaystyle \{0,1,\dots ,p-1\}}$El algoritmo recibe su 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 calcular raíces cuadradas módulo potencias primas. ^{[ 1 ]}

Entradas:

• ${\displaystyle p}$, un número primo impar,
• ${\displaystyle n\in \mathbf {F} _{p}}$, que es un cuadrado.

Salidas:

• ${\displaystyle x\in \mathbf {F} _{p}}$, satisfactorio${\displaystyle x^{2}=n.}$

El paso 1 es encontrar un${\displaystyle a\in \mathbf {F} _{p}}$de tal manera que${\displaystyle a^{2}-n}$no es un cuadrado. No se conoce ningún algoritmo determinista para encontrar tal cosa.${\displaystyle a}$, pero se puede utilizar el siguiente método de prueba y error . Simplemente elija un${\displaystyle a}$y calculando el símbolo de Legendre${\displaystyle \left({\frac {a^{2}-n}{p}}\right)}$uno puede ver si${\displaystyle a}$satisface la condición. La probabilidad de que un aleatorio${\displaystyle a}$satisfará es${\displaystyle (p-1)/2p}$. Con${\displaystyle p}$lo suficientemente grande esto es sobre${\displaystyle 1/2}$. ^{[ 2 ]} Por lo tanto, el número esperado de ensayos antes de encontrar uno adecuado${\displaystyle a}$es aproximadamente 2.

El paso 2 consiste en calcular x mediante el cálculo${\displaystyle x=\left(a+{\sqrt {a^{2}-n}}\right)^{(p+1)/2}}$dentro de la extensión de campo${\displaystyle \mathbf {F} _{p^{2}}=\mathbf {F} _{p}({\sqrt {a^{2}-n}})}$. Esta x será la que satisfaga${\displaystyle x^{2}=n.}$

Si${\displaystyle x^{2}=n}$, entonces${\displaystyle (-x)^{2}=n}$También se cumple. Y dado que p es impar,${\displaystyle x\neq -x}$. Por lo tanto, siempre que se encuentra una solución x , siempre hay una segunda solución, -x .

(Nota: Todos los elementos anteriores al paso dos se consideran como un elemento de${\displaystyle \mathbf {F} _{13}}$y todos los elementos del paso dos se consideran elementos de${\displaystyle \mathbf {F} _{13^{2}}}$.)

Encuentra todos los x tales que${\displaystyle x^{2}=10.}$

Antes de aplicar el algoritmo, debe comprobarse que${\displaystyle 10}$es de hecho un cuadrado en${\displaystyle \mathbf {F} _{13}}$Por lo tanto, el símbolo de Legendre${\displaystyle (10|13)}$debe ser igual a 1. Esto se puede calcular utilizando el criterio de Euler :${\textstyle (10|13)\equiv 10^{6}\equiv 1{\pmod {13}}.}$Esto confirma que 10 es un cuadrado perfecto y, por lo tanto, se puede aplicar el algoritmo.

• Paso 1: Encuentra un a tal que${\displaystyle a^{2}-n}$no es un cuadrado. Como se indicó, esto debe hacerse por ensayo y error. Elija${\displaystyle a=2}$. Entonces${\displaystyle a^{2}-n}$se convierte en 7. El símbolo de Legendre${\displaystyle (7|13)}$tiene que ser −1. Nuevamente, esto se puede calcular utilizando el criterio de Euler:${\textstyle 7^{6}=343^{2}\equiv 5^{2}\equiv 25\equiv -1{\pmod {13}}.}$Entonces${\displaystyle a=2}$es una opción adecuada para un .
• Paso 2: Calcular${\displaystyle x=\left(a+{\sqrt {a^{2}-n}}\right)^{(p+1)/2}=\left(2+{\sqrt {-6}}\right)^{7}}$en${\displaystyle \mathbf {F} _{13}({\sqrt {-6}})}$:

${\displaystyle \left(2+{\sqrt {-6}}\right)^{2}=4+4{\sqrt {-6}}-6=-2+4{\sqrt {-6}}}$

${\displaystyle \left(2+{\sqrt {-6}}\right)^{4}=\left(-2+4{\sqrt {-6}}\right)^{2}=-1-3{\sqrt {-6}}}$

${\displaystyle \left(2+{\sqrt {-6}}\right)^{6}=\left(-2+4{\sqrt {-6}}\right)\left(-1-3{\sqrt {-6}}\right)=9+2{\sqrt {-6}}}$

${\displaystyle \left(2+{\sqrt {-6}}\right)^{7}=\left(9+2{\sqrt {-6}}\right)\left(2+{\sqrt {-6}}\right)=6}$

Entonces${\displaystyle x=6}$es una solución, así como${\displaystyle x=-6}$. En efecto,${\textstyle 6^{2}\equiv 10{\pmod {13}}.}$

La primera parte de la prueba consiste en verificar que${\displaystyle \mathbf {F} _{p^{2}}=\mathbf {F} _{p}({\sqrt {a^{2}-n}})=\{x+y{\sqrt {a^{2}-n}}:x,y\in \mathbf {F} _{p}\}}$es de hecho un campo. En aras de la simplicidad de la notación,${\displaystyle \omega }$se define como${\displaystyle {\sqrt {a^{2}-n}}}$. Por supuesto,${\displaystyle a^{2}-n}$es un no residuo cuadrático, por lo que no hay raíz cuadrada en${\displaystyle \mathbf {F} _{p}}$. Este${\displaystyle \omega }$puede considerarse aproximadamente análogo al número complejo i . La aritmética de cuerpos es bastante obvia. La suma se define como

${\displaystyle \left(x_{1}+y_{1}\omega \right)+\left(x_{2}+y_{2}\omega \right)=\left(x_{1}+x_{2}\right)+\left(y_{1}+y_{2}\right)\omega }$.

La multiplicación también se define como de costumbre. Teniendo en cuenta que${\displaystyle \omega ^{2}=a^{2}-n}$se convierte en

${\displaystyle \left(x_{1}+y_{1}\omega \right)\left(x_{2}+y_{2}\omega \right)=x_{1}x_{2}+x_{1}y_{2}\omega +y_{1}x_{2}\omega +y_{1}y_{2}\omega ^{2}=\left(x_{1}x_{2}+y_{1}y_{2}\left(a^{2}-n\right)\right)+\left(x_{1}y_{2}+y_{1}x_{2}\right)\omega }$.

Ahora hay que comprobar las propiedades del campo. Las propiedades de cierre bajo la suma y la multiplicación, asociatividad , conmutatividad y distributividad se ven fácilmente. Esto se debe a que en este caso el campo${\displaystyle \mathbf {F} _{p^{2}}}$se asemeja un poco al campo de los números complejos (con${\displaystyle \omega }$siendo el análogo de i ). La identidad aditiva es${\displaystyle 0}$, o más formalmente${\displaystyle 0+0\omega }$: Dejar${\displaystyle \alpha \in \mathbf {F} _{p^{2}}}$, entonces

${\displaystyle \alpha +0=(x+y\omega )+(0+0\omega )=(x+0)+(y+0)\omega =x+y\omega =\alpha }$.

La identidad multiplicativa es${\displaystyle 1}$, o más formalmente${\displaystyle 1+0\omega }$:

${\displaystyle \alpha \cdot 1=(x+y\omega )(1+0\omega )=\left(x\cdot 1+0\cdot y\left(a^{2}-n\right)\right)+(x\cdot 0+1\cdot y)\omega =x+y\omega =\alpha }$.

Lo único que queda por${\displaystyle \mathbf {F} _{p^{2}}}$ser un campo es la existencia de inversos aditivos y multiplicativos . Es fácil ver que el inverso aditivo de${\displaystyle x+y\omega }$es${\displaystyle -x-y\omega }$, que es un elemento de${\displaystyle \mathbf {F} _{p^{2}}}$, porque${\displaystyle -x,-y\in \mathbf {F} _{p}}$. De hecho, esos son los elementos inversos aditivos de x e y . Para demostrar que cada elemento distinto de cero${\displaystyle \alpha }$tiene un inverso multiplicativo, escríbelo${\displaystyle \alpha =x_{1}+y_{1}\omega }$y${\displaystyle \alpha ^{-1}=x_{2}+y_{2}\omega }$. En otras palabras,

${\displaystyle (x_{1}+y_{1}\omega )(x_{2}+y_{2}\omega )=\left(x_{1}x_{2}+y_{1}y_{2}\left(a^{2}-n\right)\right)+\left(x_{1}y_{2}+y_{1}x_{2}\right)\omega =1}$.

Entonces las dos igualdades${\displaystyle x_{1}x_{2}+y_{1}y_{2}(a^{2}-n)=1}$y${\displaystyle x_{1}y_{2}+y_{1}x_{2}=0}$debe sostenerse. El cálculo de los detalles proporciona expresiones para${\displaystyle x_{2}}$y${\displaystyle y_{2}}$, es decir

${\displaystyle x_{2}=-y_{1}^{-1}x_{1}\left(y_{1}\left(a^{2}-n\right)-x_{1}^{2}y_{1}^{-1}\right)^{-1}}$,

${\displaystyle y_{2}=\left(y_{1}\left(a^{2}-n\right)-x_{1}^{2}y_{1}^{-1}\right)^{-1}}$.

Los elementos inversos que se muestran en las expresiones de${\displaystyle x_{2}}$y${\displaystyle y_{2}}$existen, porque todos estos son elementos de${\displaystyle \mathbf {F} _{p}}$. Esto completa la primera parte de la demostración, mostrando que${\displaystyle \mathbf {F} _{p^{2}}}$es un campo.

La segunda parte, la central, de la demostración consiste en mostrar que para cada elemento${\displaystyle x+y\omega \in \mathbf {F} _{p^{2}}:(x+y\omega )^{p}=x-y\omega }$. Por definición,${\displaystyle \omega ^{2}=a^{2}-n}$no es un cuadrado en${\displaystyle \mathbf {F} _{p}}$El criterio de Euler entonces dice que

${\displaystyle \omega ^{p-1}=\left(\omega ^{2}\right)^{\frac {p-1}{2}}=-1}$.

De este modo${\displaystyle \omega ^{p}=-\omega }$. Esto, junto con el pequeño teorema de Fermat (que dice que${\displaystyle x^{p}=x}$a pesar de${\displaystyle x\in \mathbf {F} _{p}}$) y el conocimiento de que en campos de característica p la ecuación${\displaystyle \left(a+b\right)^{p}=a^{p}+b^{p}}$Se mantiene, una relación a veces llamada el sueño del estudiante de primer año , muestra el resultado deseado

${\displaystyle (x+y\omega )^{p}=x^{p}+y^{p}\omega ^{p}=x-y\omega }$.

La tercera y última parte de la demostración consiste en mostrar que si${\displaystyle x_{0}=\left(a+\omega \right)^{\frac {p+1}{2}}\in \mathbf {F} _{p^{2}}}$, entonces${\displaystyle x_{0}^{2}=n\in \mathbf {F} _{p}}$Calcular ​

${\displaystyle x_{0}^{2}=\left(a+\omega \right)^{p+1}=(a+\omega )(a+\omega )^{p}=(a+\omega )(a-\omega )=a^{2}-\omega ^{2}=a^{2}-\left(a^{2}-n\right)=n}$.

Tenga en cuenta que este cálculo tuvo lugar en${\displaystyle \mathbf {F} _{p^{2}}}$, así que esto${\displaystyle x_{0}\in \mathbf {F} _{p^{2}}}$Pero con el teorema de Lagrange , que establece que un polinomio no nulo de grado n tiene como máximo n raíces en cualquier cuerpo K , y el conocimiento de que${\displaystyle x^{2}-n}$tiene 2 raíces en${\displaystyle \mathbf {F} _{p}}$, estas raíces deben ser todas las raíces en${\displaystyle \mathbf {F} _{p^{2}}}$. Se acaba de demostrar que${\displaystyle x_{0}}$y${\displaystyle -x_{0}}$son raíces de${\displaystyle x^{2}-n}$en${\displaystyle \mathbf {F} _{p^{2}}}$, así que debe ser que${\displaystyle x_{0},-x_{0}\in \mathbf {F} _{p}}$. ^{[ 3 ]}

Después de encontrar un valor adecuado de a , el número de operaciones requeridas para el algoritmo es${\displaystyle 4m+2k-4}$multiplicaciones,${\displaystyle 4m-2}$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 a por ensayo y error, el número esperado de cálculos del símbolo de Legendre es 2. Pero uno puede tener suerte en el primer intento y puede necesitar más de 2 intentos. En el campo${\displaystyle \mathbf {F} _{p^{2}}}$Se cumplen las dos igualdades siguientes.

${\displaystyle (x+y\omega )^{2}=\left(x^{2}+y^{2}\omega ^{2}\right)+\left(\left(x+y\right)^{2}-x^{2}-y^{2}\right)\omega ,}$

dónde${\displaystyle \omega ^{2}=a^{2}-n}$Se conoce de antemano. Este cálculo requiere 4 multiplicaciones y 4 sumas.

${\displaystyle \left(x+y\omega \right)^{2}\left(a+\omega \right)=\left(ad^{2}-b\left(x+d\right)\right)+\left(d^{2}-by\right)\omega ,}$

dónde${\displaystyle d=(x+ya)}$y${\displaystyle b=ny}$Esta operación requiere 6 multiplicaciones y 4 sumas.

Suponiendo que${\displaystyle p\equiv 1{\pmod {4}},}$(en el caso${\displaystyle p\equiv 3{\pmod {4}}}$, el cálculo directo${\displaystyle x\equiv \pm n^{\frac {p+1}{4}}}$es mucho más rápido) la expresión binaria de${\displaystyle (p+1)/2}$tiene${\displaystyle m-1}$dígitos, de los cuales k son unos. Entonces, para calcular un${\displaystyle (p+1)/2}$poder de${\displaystyle \left(a+\omega \right)}$, la primera fórmula debe ser utilizada${\displaystyle n-k-1}$veces y la segunda${\displaystyle k-1}$veces.

Por ello, el algoritmo de Cipolla es mejor que el algoritmo de Tonelli-Shanks si y solo si${\displaystyle S(S-1)>8m+20}$, con${\displaystyle 2^{S}}$siendo la máxima potencia de 2 que divide a${\displaystyle p-1}$. ^{[ 4 ]}

Según la "Historia de los números" de Dickson, la siguiente fórmula de Cipolla hallará raíces cuadradas módulo potencias de números primos: ^{[ 5 ] [ 6 ]}

${\displaystyle 2^{-1}q^{t}((k+{\sqrt {k^{2}-q}})^{s}+(k-{\sqrt {k^{2}-q}})^{s}){\bmod {p^{\lambda }}}}$

dónde${\displaystyle t=(p^{\lambda }-2p^{\lambda -1}+1)/2}$y${\displaystyle s=p^{\lambda -1}(p+1)/2}$

dónde${\displaystyle q=10}$,${\displaystyle k=2}$como en el ejemplo de este artículo

Tomando como ejemplo el artículo de la wiki podemos ver que esta fórmula anterior efectivamente toma raíces cuadradas módulo potencias primas.

Como

${\displaystyle {\sqrt {10}}{\bmod {13^{3}}}\equiv 1046}$

Ahora resuelve para${\displaystyle 2^{-1}q^{t}}$a través de:

${\displaystyle 2^{-1}10^{(13^{3}-2\cdot 13^{2}+1)/2}{\bmod {13^{3}}}\equiv 1086}$

Ahora crea el${\displaystyle (2+{\sqrt {2^{2}-10}})^{13^{2}\cdot 7}{\bmod {13^{3}}}}$y${\displaystyle (2-{\sqrt {2^{2}-10}})^{13^{2}\cdot 7}{\bmod {13^{3}}}}$ (Véase aquí el código de Mathematica que muestra el cálculo anterior, teniendo en cuenta que se trata de algo parecido a una aritmética modular compleja).

Tal como:

${\displaystyle (2+{\sqrt {2^{2}-10}})^{13^{2}\cdot 7}{\bmod {13^{3}}}\equiv 1540}$ y${\displaystyle (2-{\sqrt {2^{2}-10}})^{13^{2}\cdot 7}{\bmod {13^{3}}}\equiv 1540}$

y la ecuación final es:

${\displaystyle 1086(1540+1540){\bmod {13^{3}}}\equiv 1046}$ ¿Cuál es la respuesta?

• E. Bach , JO Shallit, Teoría algorítmica de números: algoritmos eficientes, MIT Press, (1996)