Test de primalidad por curvas elípticas

En matemáticas, las técnicas de prueba de primalidad mediante curvas elípticas, o tests de primalidad por curvas elípticas (ECPP por las siglas de su nombre en inglés, Elliptic Curve Primality Proving), se encuentran entre los métodos más rápidos y más utilizados en la prueba de primalidad.​ Es una idea propuesta por Shafrira Goldwasser y Joe Kilian en 1986 y convertida en algoritmo por A. O. L. Atkin ese mismo año. El algoritmo fue alterado y mejorado por varios colaboradores posteriormente, y en particular por Atkin y François Morain, en 1993.​ El concepto de usar curvas elípticas en la factorización había sido desarrollado por H. W. Lenstra en 1985, y las implicaciones para su uso en pruebas (y demostraciones) de primalidad siguieron rápidamente.

Los tests de primalidad son un campo que existe desde la época de Pierre de Fermat, en cuyo tiempo la mayoría de los algoritmos se basaban en la factorización, que se vuelve difícil de manejar con números grandes. Los algoritmos modernos tratan los problemas de determinar si un número es primo y cuáles son sus factores por separado, una cuestión que se volvió de importancia práctica con el inicio de la criptografía moderna. Aunque muchas pruebas actuales dan como resultado una salida probabilística (N se muestra como compuesto o como probablemente primo, como con el test de primalidad de Baillie-PSW o el test de primalidad de Miller-Rabin), la prueba de la curva elíptica prueba la primalidad (o composición) con un certificado rápidamente verificable.​

Los métodos para demostrar la primalidad de un número conocidos anteriormente, como el test de Pocklington-Lehmer, requerían al menos una factorización parcial de $N\pm 1$ para demostrar que $N$ es primo. Como resultado, estos métodos requerían algo de suerte y generalmente son lentos en la práctica.

Primalidad mediante curvas elípticas

Es un algoritmo de uso general, lo que significa que no depende de que el número tenga una forma especial. La ECPP es actualmente en la práctica el algoritmo conocido más rápido para probar la primalidad de los números en general, pero no se conoce su tiempo de ejecución en el peor de los casos. Heurísticamente, se ejecuta en el tiempo:

$O((\log n)^{5+\varepsilon })\,$

para algunos $\varepsilon >0$.​ Este exponente puede reducirse a $4+\varepsilon$ para algunas versiones mediante argumentos heurísticos. El algoritmo funciona de la misma manera que la mayoría de los otros tests de primalidad, para lo que encuentra un grupo y muestra que su tamaño es tal que $p$ es primo. Para la ECPP, el grupo es una curva elíptica sobre un conjunto finito de formas cuadráticas, de modo que $p-1$ es trivial para la factorización sobre el grupo.

Genera un certificado de primalidad de Atkin-Goldwasser-Kilian-Morain por recursión y luego intenta verificar el certificado. El paso que requiere más tiempo de procesamiento es la generación del certificado, porque se debe realizar la factorización sobre un cuerpo de clases. El certificado se puede verificar rápidamente, lo que permite que una verificación de funcionamiento tome muy poco tiempo.

A junio de 2022, el primo más grande que se ha probado con el método ECPP es $10^{50000}+65859$.​ La certificación fue realizada por Andreas Enge usando su software fastECPP CM.

Proposición

Las pruebas de primalidad por curvas elípticas se basan en criterios análogos al criterio de Pocklington,​​ donde el grupo $(\mathbb {Z} /n\mathbb {Z} )^{*}$ se reemplaza por $E(\mathbb {Z} /n\mathbb {Z} ),$ y E es una curva elíptica elegida adecuadamente. A continuación se enuncia una proposición sobre la cual basar la prueba, que es análoga al criterio de Pocklington y da lugar a la forma de Goldwasser-Kilian-Atkin de la prueba de primalidad de la curva elíptica:

Sea N un entero positivo y E el conjunto definido por la ecuación $y^{2}=x^{3}+ax+b{\bmod {N}}.$ Considérese E sobre $\mathbb {Z} /N\mathbb {Z} ,$ aplíquese una ley de adición usual sobre E y sea 0 para el elemento neutro en E.

Sea m un número entero. Si hay un primo q que divide a m, y es mayor que $\left({\sqrt[{4}]{N}}+1\right)^{2}$ y existe un punto P en E tal que

(1) mP= 0

(2) (m/q)P está definido y no es igual a 0

Entonces N es primo.

Prueba

Si N es compuesto, entonces existe un primo $p\leq {\sqrt {N}}$ que divide a N. Defínase $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 $m_{p}$ como el orden del grupo $E_{p}$. Por el teorema sobre curvas elípticas de Hasse se sabe que

$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 $\gcd(q,m_{p})=1$ y existe un entero u con la propiedad de que

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

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

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

por (1), ya que $mP_{p}$ se calcula usando el mismo método que mP, excepto módulo p en lugar de módulo N (y $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á:​

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

Algoritmo de Goldwasser-Kilian

A partir de esta proposición se puede construir un algoritmo para demostrar que un número entero, N, es primo. Esto se hace de la siguiente manera:​

Elíjanse tres enteros al azar, a, x, y, estableciendo a continuación

$b\equiv y^{2}-x^{3}-ax{\pmod {N}}$

Ahora P= (x,y) es un punto sobre E, donde se tiene que E está definido por $y^{2}=x^{3}+ax+b$. A continuación, se necesita un algoritmo para contar el número de puntos en E. Aplicado a E, este algoritmo (Koblitz y otros sugieren el algoritmo de Schoof) produce un número m que es el número de puntos en la curva E sobre F_N, siempre que N es primo. Si el algoritmo de conteo de puntos se detiene en una expresión indefinida, esto permite determinar un factor no trivial de N. Si tiene éxito, se aplica un criterio para decidir si la curva E es aceptable.

Si se puede escribir m en la forma $m=kq$ donde $k\geq 2$ es un entero pequeño y q un primo probable grande (un número que pasa un test de primalidad probabilístico, por ejemplo), entonces no se descarta E. De lo contrario, se descarta la curva y se selecciona aleatoriamente otra tripleta (a, x, y) para comenzar de nuevo. La idea aquí es encontrar una m que sea divisible por un gran número primo q. Este número primo es unos dígitos más pequeño que m (o N), por lo que q será más fácil de probar como primo que N.

Asumiendo que se halla una curva que satisface el criterio, se procede a calcular mP y kP. Si cualquiera de los dos cálculos produce una expresión indefinida, se puede obtener un factor no trivial de N. Si ambos cálculos tienen éxito, se examinan los resultados.

Si $mP\neq 0$ es claro que N no es primo, porque si N fuera primo entonces E tendría orden m, y cualquier elemento de E se convertiría en 0 en la multiplicación por m. Si kP= 0, entonces el algoritmo descarta E y comienza de nuevo con una tripleta a, x, y diferente.

Ahora bien, si $mP=0$ y $kP\neq 0$, la proposición anterior indica que N es primo. Sin embargo, existe un posible problema, que es la primalidad de q. Esto se verifica usando el mismo algoritmo. Así que se ha descrito un procedimiento recursivo, donde la primalidad de N depende de la primalidad de q y, de hecho, de primos probables más pequeños hasta que se alcanza un umbral en el que q se considera lo suficientemente pequeño como para aplicarse un algoritmo determinista no recursivo.​​

Problemas con el algoritmo

Atkin y Morain afirman que el problema con GK es que el algoritmo de Schoof parece casi imposible de poner en práctica.​ 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.​ 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

$[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.​

Prueba de primalidad de la curva elíptica de Atkin-Morain (ECPP)

En un artículo de 1993, Atkin y Morain describieron un algoritmo ECPP que evitaba el problema de depender de un engorroso algoritmo de conteo de puntos (como el de Schoof). El algoritmo aún se basa en la proposición mencionada anteriormente, pero en lugar de generar aleatoriamente curvas elípticas y buscar una m adecuada, su idea era construir una curva E en la que el número de puntos sea fácil de calcular. La multiplicación compleja es clave en la construcción de la curva.

Ahora, dada una N para la que se necesita probar la primalidad, se necesita encontrar una m y una q adecuadas, como en la prueba de Goldwasser-Kilian, que cumplirá la proposición y probará la primalidad de N (por supuesto, también se debe encontrar un punto P y la curva misma, E).

La ECPP utiliza multiplicaciones complejas para construir la curva E, haciéndolo de una manera que permite calcular fácilmente m (el número de puntos en E). Ahora se describe este método:

La utilización de la multiplicación compleja requiere un discriminante negativo, D, tal que D se puede escribir como el producto de dos elementos $D=\pi {\bar {\pi }}$, o de manera completamente equivalente, se puede escribir la ecuación:

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

para algunos a, b. Si se puede describir N en términos de cualquiera de estas formas, es posible crear una curva elíptica E en $\mathbb {Z} /N\mathbb {Z}$ con la multiplicación compleja (descrita en detalle a continuación), y el número de puntos viene dado por:

$|E(\mathbb {Z} /N\mathbb {Z} )|=N+1-\pi -{\bar {\pi }}=N+1-a.\,$

Para que N se divida en los dos elementos, se necesita que $\left({\frac {D}{N}}\right)=1$ (donde $\left({\frac {D}{N}}\right)$ denota el símbolo de Legendre). Esta es una condición necesaria, y se logra la suficiencia si la clase numérica h(D) del orden en $\mathbb {Q} ({\sqrt {D}})$ es 1. Esto sucede solo para 13 valores de D, que son los elementos de {−3, −4, −7, −8, −11, −12, −16, −19, −27, −28, −43, −67, −163}

La prueba

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

$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 $m=N+1-a$. Ahora bien, si m tiene un factor primo q de tamaño

$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.​

Método de multiplicación complejo

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 $D\neq -3$ y $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 $H_{D}(X)$, cuyas raíces corresponden a los valores h(D). Téngase en cuenta que $H_{D}(X)$ es una clase polinómica. A partir de la teoría de la multiplicación compleja, se sabe que $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 $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:

$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

$|E(\mathbb {Z} /N\mathbb {Z} )|=N+1-a$ o $|E(\mathbb {Z} /N\mathbb {Z} )|=N+1+a$​​​

Discusión

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.

Ejemplo de Atkin-Morain ECPP

Se construye un ejemplo para probar que $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 $(D/N)=1$ y si 4N se puede escribir como $4N=a^{2}+|D|b^{2}$.

Para el ejemplo se elige $D=-43$. Esto se debe a que $(D/N)=(-43/167)=1$ y también, usando el algoritmo de Cornacchia, se sabe que $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 $m=N+1-a$, lo que da como resultado $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 $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.​ Afirma que dado el valor m, se busca un s que divida a m, $s>(N^{1/4}+1)^{2}$, pero que no sea necesariamente primo, y se verifica si, para cada $p_{i}$ que divide a s

$(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 $p_{i}$ son 11 y 13. Primero, está claro que $143>(167^{1/4}+1)^{2}$, por lo que solo se necesita verificar los valores de

$(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

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

A continuación se calcula

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

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

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

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

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

de donde resulta

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

Ahora, utilizando el punto P= (6,6) en E se puede verificar que $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.

Complejidad y tiempos de ejecución

El algoritmo de prueba de primalidad de la curva elíptica de Goldwasser y Kilian termina en tiempo polinomial esperado durante al menos

$1-O\left(2^{-N{\frac {1}{\log \log n}}}\right)$

de entradas principales.

Conjetura

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

$\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 $O(k^{2})$ que se puede verificar en $O(k^{4})$.​

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

Conjetura 2

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

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

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

$O(\log ^{10+c_{2}}n)$​

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

$O((\log N)^{6+\epsilon })$ para algunos $\epsilon >0$​

Primos de forma especial

Para algunas formas de números, es posible encontrar "atajos" a una prueba de primalidad. Este es el caso de los números primos de Mersenne. De hecho, debido a su estructura especial, que permite una verificación más sencilla de la primalidad, los seis números primos más grandes conocidos son todos números de Mersenne.​ Ha habido un método en uso durante algún tiempo para verificar la primalidad de los números de Mersenne, conocido como test de Lucas-Lehmer. Esta prueba no se basa en curvas elípticas. Sin embargo, aquí se presenta un resultado en el que números de la forma $N=2^{k}n-1$ donde $k,n\in \mathbb {Z} ,k\geq 2$, n impares pueden demostrarse como primos (o compuestos) usando curvas elípticas. Por supuesto, esto también proporcionará un método para probar la primalidad de los números de Mersenne, que corresponden al caso donde n= 1. El siguiente método se extrae del artículo Prueba de primalidad para $2^{k}n-1$ usando curvas elípticas, por Yu Tsumura.​

Estructura de grupo de E(F_N)

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

Teorema 1.​ $E(\mathbb {F} _{p})=p+1.$

Teorema 2. $E(\mathbb {F} _{p})\cong \mathbb {Z} _{2^{k}n}$ o $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 $2^{k}$ en el grupo cíclico $E(\mathbb {F} _{p})\cong \mathbb {Z} _{2^{k}n}.$

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

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

$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 $\gcd {(S_{i},p)}=1$ para i = 1, 2, ...,k − 1 y $S_{k}\equiv 0{\pmod {p}},$ donde $S_{i}$ es una secuencia con valor inicial $S_{0}=x$.

El algoritmo

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

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

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

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

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

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

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

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

Justificación del algoritmo

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

$\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 $2^{k}$, por el Teorema 3, y por lo tanto el orden de Q' es $2^{k}d$ d|n.

Esto significa que Q= nQ' tiene el orden $2^{k}$. Por lo tanto, si (1) concluye que N es compuesto, realmente es compuesto. (2) y (3) permiten comprobar si Q tiene orden $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 $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.​

Enlaces externos

• Elliptic Curves and Primality Proving by Atkin and Morain.
• Weisstein, Eric W. «Elliptic Curve Primality Proving». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research. 
• Chris Caldwell, "Primality Proving 4.2: Elliptic curves and the ECPP test" at the Prime Pages.
• François Morain, "The ECPP home page" (includes old ECPP software for some architectures).
• Marcel Martin, "Primo" (binary for Linux 64-bit)
• PARI/GP, a computer algebra system with functions to create Atkin-Morain and Primo primality certificates
• GMP-ECPP, a free ECPP implementation
• LiDIA, a free C++ library for Linux with ECPP support
• CM Archivado el 7 de mayo de 2022 en Wayback Machine., another free library that contains an ECPP implementation

• Datos: Q3611581