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.Top, Jaap, Elliptic Curve Primality Proving, http://www.math.rug.nl/~top/atkin.pdf 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.Atkin, A.O.L., Morain, F., Elliptic Curves and Primality Proving, https://www.ams.org/mcom/1993-61-203/S0025-5718-1993-1199989-X/S0025-5718-1993-1199989-X.pdf

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 para demostrar que 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:

para algunos . Este exponente puede reducirse a 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 es primo. Para la ECPP, el grupo es una curva elíptica sobre un conjunto finito de formas cuadráticas, de modo que 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.

, el primo más grande que se ha probado con el método ECPP es .Caldwell, Chris. The Top Twenty: Elliptic Curve Primality Proof from the Prime Pages. 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,Washington, Lawrence C., Elliptic Curves: Number Theory and Cryptography, Chapman & Hall/CRC, 2003 donde el grupo se reemplaza por 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 Considérese E sobre 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 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 que divide a N. Defínase 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 como el orden del grupo . Por el teorema sobre curvas elípticas de Hasse se sabe que

y por lo tanto y existe un entero u con la propiedad de que

Sea el punto P evaluado módulo p. Así, en se tiene que

por (1), ya que se calcula usando el mismo método que mP, excepto módulo p en lugar de módulo N (y ).

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á:Koblitz, Neal, Introduction to Number Theory and Cryptography, 2nd Ed, Springer, 1994

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

Ahora P= (x,y) es un punto sobre E, donde se tiene que E está definido por . 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 FN, 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 donde 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 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 y , 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.m418oh27.pdfBlake, Ian F., Seroussi, Gadiel, Smart, Nigel Paul, Elliptic Curves in Cryptography, Cambridge University Press, 1999

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.Lenstra, Hendrik W., Efficient Algorithms in Number Theory, https://openaccess.leidenuniv.nl/bitstream/1887/2141/1/346_081.pdf 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

,

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 , o de manera completamente equivalente, se puede escribir la ecuación:

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 con la multiplicación compleja (descrita en detalle a continuación), y el número de puntos viene dado por:

Para que N se divida en los dos elementos, se necesita que (donde 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 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 y si 4N se pueden escribir como:

Esta parte se puede verificar usando el algoritmo de Cornacchia. Una vez que se han hallado D y a aceptables, calcúlese . Ahora bien, si m tiene un factor primo q de tamaño

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 y (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 , cuyas raíces corresponden a los valores h(D). Téngase en cuenta que es una clase polinómica. A partir de la teoría de la multiplicación compleja, se sabe que tiene coeficientes enteros, lo que permite estimar estos coeficientes con la precisión suficiente para descubrir sus valores verdaderos.