Test de primalidad por curvas elípticas

Si N es compuesto, entonces existe un primo ${\displaystyle p\leq {\sqrt {N}}}$ que divide a N. Defínase ${\displaystyle E_{p}}$ como la curva elíptica definida por la misma ecuación que E pero evaluada módulo p en lugar de módulo N. Définase también ${\displaystyle m_{p}}$ como el orden del grupo ${\displaystyle E_{p}}$. Por el teorema sobre curvas elípticas de Hasse se sabe que

${\displaystyle m_{p}\leq p+1+2{\sqrt {p}}=\left({\sqrt {p}}+1\right)^{2}\leq \left({\sqrt[{4}]{N}}+1\right)^{2}<q}$

y por lo tanto ${\displaystyle \gcd(q,m_{p})=1}$ y existe un entero u con la propiedad de que

${\displaystyle uq\equiv 1{\bmod {m_{p}}}.}$

Sea ${\displaystyle P_{p}}$ el punto P evaluado módulo p. Así, en ${\displaystyle E_{p}}$ se tiene que

${\displaystyle (m/q)P_{p}=uq(m/q)P_{p}=umP_{p}=0,}$

por (1), ya que ${\displaystyle mP_{p}}$ se calcula usando el mismo método que mP, excepto módulo p en lugar de módulo N (y ${\displaystyle p\mid N}$).

Esto contradice (2), porque si (m/q)P está definido y no es igual a 0 (mod N), entonces con el mismo método se calcula módulo p en lugar de módulo N que producirá:[8]

${\displaystyle (m/q)P_{p}\neq 0.}$

Atkin y Morain afirman que el problema con GK es que el algoritmo de Schoof parece casi imposible de poner en práctica.[3] Es muy lento y engorroso contar todos los puntos en E usando el algoritmo de Schoof, que es el algoritmo preferido para el algoritmo de Goldwasser-Kilian. Sin embargo, el algoritmo original de Schoof no es lo suficientemente eficiente para proporcionar una gran cantidad de puntos en poco tiempo.[11] Estos comentarios deben situarse en su contexto histórico, antes de las mejoras de Elkies y Atkin al método de Schoof.

Un segundo problema que señala Koblitz es la dificultad de encontrar la curva E cuyo número de puntos es de la forma kq, como se indicó anteriormente. No existe un teorema conocido que garantice que se pueda encontrar una E adecuada en muchos intentos polinómicos. La distribución de números primos en el intervalo de Hasse

${\displaystyle [p+1-2{\sqrt {p}},p+1+2{\sqrt {p}}]}$,

que contiene m, no es la misma que la distribución de primos en los órdenes de grupo, contando curvas con multiplicidad. Sin embargo, esto no es un problema significativo en la práctica.[8]

Elíjanse los discriminantes D en secuencia de aumento de h(D). Para cada D, compruébese si ${\displaystyle \left({\frac {D}{N}}\right)=1}$ y si 4N se pueden escribir como:

${\displaystyle a^{2}+|D|b^{2}=4N\,}$

Esta parte se puede verificar usando el algoritmo de Cornacchia. Una vez que se han hallado D y a aceptables, calcúlese ${\displaystyle m=N+1-a}$. Ahora bien, si m tiene un factor primo q de tamaño

${\displaystyle q>(N^{1/4}+1)^{2}}$

se debe usar el método de la multiplicación compleja para construir la curva E y un punto P en ella. Entonces se puede usar la proposición para verificar la primalidad de N. Téngase en cuenta que si m no tiene un factor primo grande o no se puede factorizar lo suficientemente rápido, se puede hacer otra elección de D.[1]

Para completar la explicación, se va a proporcionar una descripción general de la multiplicación compleja, la forma en que se puede crear una curva elíptica, dada una D (que se puede escribir como un producto de dos elementos).

Supóngase primero que ${\displaystyle D\neq -3}$ y ${\displaystyle D\neq -4}$ (estos casos son mucho más fáciles de calcular). Es necesario determinar los j-invariantes elípticos de las clases h(D) del orden del discriminante D como números complejos. Hay varias fórmulas para calcularlos.

A continuación, créese el monomio ${\displaystyle H_{D}(X)}$, cuyas raíces corresponden a los valores h(D). Téngase en cuenta que ${\displaystyle H_{D}(X)}$ es una clase polinómica. A partir de la teoría de la multiplicación compleja, se sabe que ${\displaystyle H_{D}(X)}$ tiene coeficientes enteros, lo que permite estimar estos coeficientes con la precisión suficiente para descubrir sus valores verdaderos.

Ahora, si N es primo, CM indica que ${\displaystyle H_{D}(X)}$ divide en módulo N en un producto de factores lineales h(D), basado en el hecho de que se eligió D para que N se divida como el producto de dos elementos. Ahora bien, si j es una de las raíces h(D) módulo N se puede definir E como:

${\displaystyle y^{2}=x^{3}-3kc^{2r}x+2kc^{3r},{\text{where }}k={\frac {j}{j-1728}},}$

c es cualquier mod no residuo cuadrático N, y r es 0 o 1.

Dada una raíz j, solo hay dos posibles elecciones no isomórficas de E, una para cada elección de r. Se tiene la cardinalidad de estas curvas como

${\displaystyle |E(\mathbb {Z} /N\mathbb {Z} )|=N+1-a}$ o ${\displaystyle |E(\mathbb {Z} /N\mathbb {Z} )|=N+1+a}$[1][10][12]

Al igual que con la prueba de Goldwasser-Killian, esta conduce a un procedimiento de ejecución descendente. De nuevo, el culpable es q. Una vez que se encuentra un q que satisface la condición, se debe verificar que sea primo, así que de hecho ahora se está haciendo toda la prueba para q. Por otra parte, es posible que se tenga que realizar la prueba de los factores de q. Esto lleva a un certificado anidado donde en cada nivel se tiene una curva elíptica E, una m y el primo en duda, q.

Se construye un ejemplo para probar que ${\displaystyle N=167}$ es primo utilizando la prueba ECPP de Atkin-Morain. Primero, procédase a través del conjunto de 13 discriminantes posibles, probando si el símbolo de Legendre ${\displaystyle (D/N)=1}$ y si 4N se puede escribir como ${\displaystyle 4N=a^{2}+|D|b^{2}}$.

Para el ejemplo se elige ${\displaystyle D=-43}$. Esto se debe a que ${\displaystyle (D/N)=(-43/167)=1}$ y también, usando el algoritmo de Cornacchia, se sabe que ${\displaystyle 4\cdot (167)=25^{2}+(43)(1^{2})}$ y por lo tanto a= 25 y b= 1.

El siguiente paso es calcular m. Esto se hace fácilmente como ${\displaystyle m=N+1-a}$, lo que da como resultado ${\displaystyle m=167+1-25=143.}$. A continuación, se necesita encontrar un probable divisor primo de m, al que se va a denominar q. Debe cumplir la condición de que ${\displaystyle q>(N^{1/4}+1)^{2}.}$

En este caso m= 143= 11×13. Desafortunadamente, no se puede elegir 11 o 13 como la q buscada, ya que no satisface la desigualdad necesaria. Sin embargo, existe una proposición análoga a la que se enunció acerca del algoritmo de Goldwasser-Kilian, que proviene de un artículo de Morain.[13] Afirma que dado el valor m, se busca un s que divida a m, ${\displaystyle s>(N^{1/4}+1)^{2}}$, pero que no sea necesariamente primo, y se verifica si, para cada ${\displaystyle p_{i}}$ que divide a s

${\displaystyle (m/p_{i})P\neq P_{\infty }}$

para algún punto P en la curva aún por construir.

Si s satisface la desigualdad y sus factores primos satisfacen lo anterior, entonces N es primo.

Entonces, en este caso, se elige s = m = 143. Por lo tanto, los posibles ${\displaystyle p_{i}}$ son 11 y 13. Primero, está claro que ${\displaystyle 143>(167^{1/4}+1)^{2}}$, por lo que solo se necesita verificar los valores de

${\displaystyle (143/11)P=13P\qquad {\text{and }}\qquad (143/13)P=11P.}$

Pero antes de que se pueda hacer esto, se debe construir la curva y elegir un punto P. Para construir la curva, se hace uso de la multiplicación compleja. En el caso estudiado se calcula el J-invariante

${\displaystyle j\equiv -960^{3}{\pmod {167}}\equiv 107{\pmod {167}}.}$

A continuación se calcula

${\displaystyle k={\frac {j}{1728-j}}{\pmod {167}}\equiv 158{\pmod {167}}}$

y se sabe que la curva elíptica es de la forma:

${\displaystyle y^{2}=x^{3}+3kc^{2}x+2kc^{3}}$,

donde k es como se describió anteriormente y c no es un cuadrado en ${\displaystyle \mathbb {F} _{167}}$. Así que se puede empezar con

${\displaystyle {\begin{aligned}r&=0\\3k&\equiv 140{\pmod {167}}\\2k&\equiv 149{\pmod {167}}\end{aligned}}}$

de donde resulta

${\displaystyle E:y^{2}=x^{3}+140x+149{\pmod {167}}}$

Ahora, utilizando el punto P= (6,6) en E se puede verificar que ${\displaystyle 143P=P_{\infty }.}$

Es sencillo comprobar que 13(6, 6)= (12, 65) y 11P= (140, 147), y así, por la proposición de Morain, N es primo.

Sea ${\displaystyle \pi (x)}$ el número de primos menores que x

${\displaystyle \exists c_{1},c_{2}>0:\pi (x+{\sqrt {x}})-\pi (x)\geq {\frac {c_{2}{\sqrt {x}}}{\log ^{c_{1}}x}}}$

para x suficientemente grande.

Si se acepta esta conjetura, el algoritmo de Goldwasser-Kilian termina en el tiempo polinomial esperado para cada entrada. Además, si la N tiene una longitud de k, entonces el algoritmo crea un certificado de tamaño ${\displaystyle O(k^{2})}$ que se puede verificar en ${\displaystyle O(k^{4})}$.[14]

Ahora considérese otra conjetura, que permitirá obtener un límite en el tiempo total del algoritmo.

Supóngase que existen constantes positivas ${\displaystyle c_{1}}$ y ${\displaystyle c_{2}}$ tales que la cantidad de números primos en el intervalo

${\displaystyle [x,x+{\sqrt {2x}}],x\geq 2}$ es mayor que ${\displaystyle c_{1}{\sqrt {x}}(\log x)^{-c_{2}}}$

Entonces el algoritmo de Goldwasser Kilian prueba la primalidad de N en un tiempo esperado de

${\displaystyle O(\log ^{10+c_{2}}n)}$[13]

Para el algoritmo de Atkin-Morain, el tiempo de ejecución indicado es

${\displaystyle O((\log N)^{6+\epsilon })}$ para algunos ${\displaystyle \epsilon >0}$[3]

Se toma E como la curva elíptica buscada, donde E tiene la forma ${\displaystyle y^{2}=x^{3}-mx}$ para ${\displaystyle m\in \mathbb {Z} ,m\not \equiv 0{\bmod {p}},}$ donde ${\displaystyle p\equiv 3{\bmod {4}}}$ es primo y ${\displaystyle p+1=2^{k}n,}$ con ${\displaystyle k\in \mathbb {Z} ,k\geq 2,n}$ impar.

Teorema 1.[7] ${\displaystyle E(\mathbb {F} _{p})=p+1.}$

Teorema 2. ${\displaystyle E(\mathbb {F} _{p})\cong \mathbb {Z} _{2^{k}n}}$ o ${\displaystyle E(\mathbb {F} _{p})\cong \mathbb {Z} _{2}\oplus \mathbb {Z} _{2^{k-1}n}}$ según que m sea o no residuo cuadrático módulo p.

Teorema 3. Sea Q= (x,y) sobre E tal que x sea un no residuo cuadrático módulo p. Entonces el orden de Q es divisible por ${\displaystyle 2^{k}}$ en el grupo cíclico ${\displaystyle E(\mathbb {F} _{p})\cong \mathbb {Z} _{2^{k}n}.}$

Primero se presenta el caso donde n es relativamente pequeño con respecto a ${\displaystyle 2^{k}}$, y esto requerirá un teorema más:

Teorema 4. Elíjase un ${\displaystyle \lambda >1}$ y supóngase que

${\displaystyle n\leq {\frac {\sqrt {p}}{\lambda }}\qquad {\text{and}}\qquad \lambda {\sqrt {p}}>\left({\sqrt[{4}]{p}}+1\right)^{2}.}$

Entonces p es primo si y solo si existe una Q= (x,y) en E, tal que ${\displaystyle \gcd {(S_{i},p)}=1}$ para i = 1, 2, ...,k − 1 y ${\displaystyle S_{k}\equiv 0{\pmod {p}},}$ donde ${\displaystyle S_{i}}$ es una secuencia con valor inicial ${\displaystyle S_{0}=x}$.

Se proporciona el siguiente algoritmo, que se basa principalmente en los teoremas 3 y 4. Para verificar la primalidad de un número dado ${\displaystyle N}$, realícense los siguientes pasos:

(1) Elíjase ${\displaystyle x\in \mathbb {Z} }$ tal que ${\displaystyle \left({\frac {x}{N}}\right)=-1}$, y encuéntrese ${\displaystyle y\in \mathbb {Z} ,y\not \equiv 0{\pmod {2}}}$ tal que ${\displaystyle \left({\frac {x^{3}-y^{2}}{N}}\right)=1}$.

Tómese ${\displaystyle m={\frac {x^{3}-y^{2}}{x}}\mod N}$ y ${\displaystyle m\not \equiv 0{\pmod {N}}}$.

Entonces ${\displaystyle Q'=(x,y)}$ está en ${\displaystyle E:y^{2}=x^{3}-mx}$.

Calcular ${\displaystyle Q=nQ'}$. Si ${\displaystyle Q\in E}$ entonces ${\displaystyle N}$ es compuesto, de lo contrario pásese a (2).

(2) Establecer ${\displaystyle S_{i}}$ como la secuencia con valor inicial ${\displaystyle Q}$. Calcúlese ${\displaystyle S_{i}}$ para ${\displaystyle i=}$${\displaystyle 1,2,3,...,k-1}$.

Si ${\displaystyle \gcd({S_{i},N})>1}$ para un ${\displaystyle i}$, donde ${\displaystyle 1\leq i\leq k-1}$ entonces ${\displaystyle N}$ es compuesto. De lo contrario, pásese a (3).

(3) Si ${\displaystyle S_{k}\equiv 0{\pmod {N}}}$ entonces ${\displaystyle N}$ es primo. De lo contrario, ${\displaystyle N}$ es compuesto. Esto completa la prueba.

En (1), se selecciona una curva elíptica, E, junto con un punto Q en E, tal que la coordenada x de Q es un no residuo cuadrático. Se puede decir que

${\displaystyle \left({\frac {m}{N}}\right)=\left({\frac {\frac {x^{3}-y^{2}}{x}}{N}}\right)=\left({\frac {x}{N}}\right)\left({\frac {x^{3}-y^{2}}{N}}\right)=-1\cdot 1=-1.}$

Así, si N es primo, Q' tiene un orden divisible por ${\displaystyle 2^{k}}$, por el Teorema 3, y por lo tanto el orden de Q' es ${\displaystyle 2^{k}d}$ d|n.

Esto significa que Q= nQ' tiene el orden ${\displaystyle 2^{k}}$. Por lo tanto, si (1) concluye que N es compuesto, realmente es compuesto. (2) y (3) permiten comprobar si Q tiene orden ${\displaystyle 2^{k}}$. Por lo tanto, si (2) o (3) concluyen que N es compuesto, es compuesto.

Ahora, si el algoritmo concluye que N es primo, entonces eso significa que ${\displaystyle S_{1}}$ satisface la condición del teorema 4, por lo que N es verdaderamente primo.

También hay un algoritmo para cuando n es grande; sin embargo, para ello se remite al mencionado artículo.[16]