Como resultado, estos métodos requerían algo de suerte y generalmente son lentos en la práctica.
A junio de 2022, el primo más grande que se ha probado con el método ECPP es
y existe un punto P en E tal que Entonces N es primo.
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
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] 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:[6] 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.
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.
La idea aquí es encontrar una m que sea divisible por un gran número primo q.
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, 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).
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.
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
Esta es una condición necesaria, y se logra la suficiencia si la clase numérica h(D) del orden en
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.
Ahora bien, si j es una de las raíces h(D) módulo N se puede definir E como: c es cualquier mod no residuo cuadrático N, y r es 0 o 1.
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.
que divide a s para algún punto P en la curva aún por construir.
Si se acepta esta conjetura, el algoritmo de Goldwasser-Kilian termina en el tiempo polinomial esperado para cada entrada.
[14] Ahora considérese otra conjetura, que permitirá obtener un límite en el tiempo total del algoritmo.
Sin embargo, aquí se presenta un resultado en el que números de la forma
, n impares pueden demostrarse como primos (o compuestos) usando curvas elípticas.
El siguiente método se extrae del artículo Prueba de primalidad para
Primero se presenta el caso donde n es relativamente pequeño con respecto a
Se puede decir que Así, si N es primo, Q' tiene un orden divisible por
También hay un algoritmo para cuando n es grande; sin embargo, para ello se remite al mencionado artículo.