Primalidad de la curva elíptica

Métodos para comprobar la primalidad

En matemáticas , las técnicas de prueba de primalidad de curva elíptica ^{, o demostración de primalidad de curva elíptica (ECPP), se encuentran entre los métodos más rápidos y más utilizados en la demostración de primalidad. [1]} Es una idea propuesta por Shafi Goldwasser y Joe Kilian en 1986 y convertida en un algoritmo por AOL Atkin el mismo año. El algoritmo fue alterado y mejorado por varios colaboradores posteriormente, y notablemente por Atkin y François Morain  [de] , en 1993. ^[2] El concepto de usar curvas elípticas en la factorización había sido desarrollado por HW Lenstra en 1985, y las implicaciones para su uso en pruebas (y demostraciones) de primalidad siguieron rápidamente.

La prueba de primalidad es un campo que ha existido desde la época de Fermat , en cuyo tiempo la mayoría de los algoritmos se basaban en factorización, que se vuelven difíciles de manejar con una gran cantidad de entrada ; los algoritmos modernos tratan los problemas de determinar si un número es primo y cuáles son sus factores por separado. Adquirió importancia práctica con el advenimiento de la criptografía moderna. Aunque muchas pruebas actuales dan como resultado una salida probabilística ( N se muestra compuesto o probablemente primo, como con la prueba de primalidad de Baillie-PSW o la prueba de Miller-Rabin ), la prueba de curva elíptica demuestra la primalidad (o composición) con un certificado rápidamente verificable. ^[3]

Los métodos de demostración de primalidad conocidos anteriormente, como la prueba de primalidad de Pocklington, 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, por lo general, son lentos en la práctica. ${\displaystyle N\pm 1}$ ${\displaystyle N}$

Demostración de primalidad de curva elíptica

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

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

para algunos . ^[4] Este exponente puede reducirse a para algunas versiones mediante argumentos heurísticos. ECPP funciona de la misma manera que la mayoría de las otras pruebas de primalidad , encontrando un grupo y mostrando que su tamaño es tal que es primo. Para ECPP, el grupo es una curva elíptica sobre un conjunto finito de formas cuadráticas tal que es trivial de factorizar sobre el grupo. ${\displaystyle \varepsilon >0}$ ${\displaystyle 4+\varepsilon }$ ${\displaystyle p}$ ${\displaystyle p-1}$

ECPP genera un certificado de primalidad Atkin – Goldwasser – Kilian – Morain mediante recursión y luego intenta verificar el certificado. El paso que consume más tiempo de CPU es la generación del certificado, porque se debe realizar la factorización sobre un campo de clase . El certificado se puede verificar rápidamente, lo que permite que la comprobación de la operación tome muy poco tiempo.

A partir de mayo de 2023 ^[actualizar], el primo más grande que se ha demostrado con el método ECPP es . ^[5] La certificación fue realizada por Andreas Enge utilizando su software fastECPP CM . ${\displaystyle 5^{104824}+104824^{5}}$

Proposición

Las pruebas de primalidad de curva elíptica se basan en criterios análogos al criterio de Pocklington, en el que se basa dicha prueba, ^{[6] [7]} donde el grupo se reemplaza por y E es una curva elíptica elegida adecuadamente. Ahora enunciaremos una proposición en la que basar nuestra prueba, que es análoga al criterio de Pocklington y da lugar a la forma Goldwasser-Kilian-Atkin de la prueba de primalidad de curva elíptica. ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{*}}$ ${\displaystyle E(\mathbb {Z} /n\mathbb {Z} ),}$

Sea N un entero positivo y E el conjunto definido por la ecuación Considere E sobre el uso de la ley de adición habitual en E y escriba 0 para el elemento neutro en E. ${\displaystyle y^{2}=x^{3}+ax+b{\bmod {N}}.}$ ${\displaystyle \mathbb {Z} /N\mathbb {Z} ,}$

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

(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. Se define como la curva elíptica definida por la misma ecuación que E pero evaluada módulo  p en lugar de módulo  N. Se define como el orden del grupo . Por el teorema de Hasse sobre curvas elípticas sabemos ${\displaystyle p\leq {\sqrt {N}}}$ ${\displaystyle E_{p}}$ ${\displaystyle m_{p}}$ ${\displaystyle E_{p}}$

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

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

Sea el punto P evaluado módulo p . Por lo tanto, en tenemos ${\displaystyle P_{p}}$ ${\displaystyle E_{p}}$

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

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

Esto contradice (2), porque si ( m / q ) P está definido y no es igual a 0 (mod  N ), entonces el mismo método calculado módulo  p en lugar de módulo  N dará como resultado: ^[8]

${\displaystyle (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 entero, N , es primo. Esto se hace de la siguiente manera: ^[6]

Elige tres números enteros al azar, a, x, y y establece

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

Ahora P = ( x , y ) es un punto en E , donde tenemos que E está definido por . A continuación necesitamos 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 sea primo. Si el algoritmo de conteo de puntos se detiene en una expresión no definida, esto permite determinar un factor no trivial de N . Si tiene éxito, aplicamos un criterio para decidir si nuestra curva E es aceptable. ${\displaystyle y^{2}=x^{3}+ax+b}$

Si podemos escribir m en la forma donde es un entero pequeño y q un primo probable grande (un número que pasa una prueba de primalidad probabilística , por ejemplo), entonces no descartamos E. De lo contrario, descartamos nuestra curva y seleccionamos aleatoriamente otra terna (a, x, y) para comenzar de nuevo. La idea aquí es encontrar un m que sea divisible por un número primo grande q . Este primo es unos pocos dígitos más pequeño que m (o N ), por lo que será más fácil demostrar que q es primo que N. ${\displaystyle m=kq}$ ${\displaystyle k\geq 2}$

Suponiendo que encontramos una curva que cumple el criterio, procedemos a calcular mP y kP . Si cualquiera de los dos cálculos produce una expresión indefinida, podemos obtener un factor no trivial de N. Si ambos cálculos son correctos, examinamos los resultados.

Si está claro que N no es primo, porque si N lo fuera entonces E tendría orden m , y cualquier elemento de E se convertiría en 0 al multiplicarlo por m . Si kP = 0, entonces el algoritmo descarta E y comienza de nuevo con una terna a, x, y diferente . ${\displaystyle mP\neq 0}$

Ahora bien, si y entonces nuestra proposición anterior nos dice que N es primo. Sin embargo, hay un problema posible, que es la primalidad de q . Esto se verifica utilizando el mismo algoritmo. Así que hemos descrito un algoritmo recursivo , donde la primalidad de N depende de la primalidad de q y de los "primos probables" más pequeños hasta que se alcanza un umbral donde q se considera lo suficientemente pequeño como para aplicar un algoritmo determinista no recursivo. ^{[9] [10]} ${\displaystyle mP=0}$ ${\displaystyle kP\neq 0}$

Problemas con el algoritmo

Atkin y Morain afirman que "el problema con GK es que el algoritmo de Schoof parece casi imposible de implementar". ^[3] Es muy lento y engorroso contar todos los puntos de E utilizando el algoritmo de Schoof, que es el algoritmo preferido para el algoritmo Goldwasser-Kilian. Sin embargo, el algoritmo original de Schoof no es lo suficientemente eficiente como para proporcionar el número de puntos en poco tiempo. ^[11] Estos comentarios deben verse en el 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 sea de la forma kq , como se indica más arriba. No se conoce ningún teorema que garantice que podemos encontrar una E adecuada en un número polinomial de intentos. La distribución de 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 las curvas con multiplicidad. Sin embargo, esto no es un problema significativo en la práctica. ^[8] ${\displaystyle [p+1-2{\sqrt {p}},p+1+2{\sqrt {p}}]}$

Prueba de primalidad de 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 algoritmo de conteo de puntos engorroso (el de Schoof). El algoritmo todavía se basa en la proposición mencionada anteriormente, pero en lugar de generar curvas elípticas aleatoriamente y buscar una m adecuada , su idea era construir una curva E donde el número de puntos fuera fácil de calcular. La multiplicación compleja es clave en la construcción de la curva.

Ahora bien, dado un N para el cual se necesita demostrar la primalidad, necesitamos encontrar un m y un q adecuados , tal como en la prueba de Goldwasser-Kilian, que cumplan la proposición y demuestren la primalidad de N. (Por supuesto, también se deben encontrar un punto P y la curva misma, E ).

La ECPP utiliza una multiplicación compleja para construir la curva E , de forma que permite calcular fácilmente m (la cantidad de puntos de E ). A continuación, describiremos este método:

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

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

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

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

Para que N se descomponga en dos elementos, necesitamos que (donde denota el símbolo de Legendre ). Esta es una condición necesaria, y logramos la suficiencia si el número de clase 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} ${\displaystyle \left({\frac {D}{N}}\right)=1}$ ${\displaystyle \left({\frac {D}{N}}\right)}$ ${\displaystyle \mathbb {Q} ({\sqrt {D}})}$

La prueba

Elija discriminantes D en secuencia de h ( D ) crecientes. Para cada D, compruebe si 4 N puede escribirse como: ${\displaystyle \left({\frac {D}{N}}\right)=1}$

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

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

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

Utilizamos el método de multiplicación compleja para construir la curva E y un punto P sobre ella. Luego podemos usar nuestra proposición para verificar la primalidad de N. Nótese que si m no tiene un factor primo grande o no se puede factorizar con la suficiente rapidez, se puede hacer otra elección de D. ^[1]

Método de multiplicación compleja

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

Supongamos primero que y (estos casos son mucho más fáciles de realizar). Es necesario calcular 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. ${\displaystyle D\neq -3}$ ${\displaystyle D\neq -4}$

A continuación, creamos el polinomio mónico , que tiene raíces correspondientes a los valores h ( D ). Nótese que es el polinomio de clase. A partir de la teoría de la multiplicación compleja, sabemos que tiene coeficientes enteros, lo que nos permite estimar estos coeficientes con la precisión suficiente para descubrir sus valores verdaderos. ${\displaystyle H_{D}(X)}$ ${\displaystyle H_{D}(X)}$ ${\displaystyle H_{D}(X)}$

Ahora bien, si N es primo, CM nos dice que descompone módulo  N en un producto de h ( D ) factores lineales, basándose en el hecho de que D fue elegido de modo que N se descomponga como el producto de dos elementos. Ahora bien, si j es una de las h ( D ) raíces módulo N podemos definir E como: ${\displaystyle H_{D}(X)}$

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

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

Dada una raíz j, sólo hay dos posibles opciones no isomorfas de E , una para cada opción de r . Tenemos la cardinalidad de estas curvas como

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

Discusión

Al igual que con la prueba Goldwasser-Killian, esta conduce a un procedimiento de ejecución descendente. Nuevamente, el culpable es q . Una vez que encontramos un q que funciona, debemos verificar que sea primo, por lo que, de hecho, ahora estamos haciendo toda la prueba para q . Luego, nuevamente, es posible que tengamos que realizar la prueba para los factores de q . Esto conduce a un certificado anidado donde en cada nivel tenemos una curva elíptica E , una m y el primo en duda,  q .

Ejemplo de ECPP Atkin-Morain

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

Para nuestro ejemplo se ha elegido . Esto se debe a que y además, utilizando el algoritmo de Cornacchia , sabemos que y por lo tanto a = 25 y b = 1. ${\displaystyle D=-43}$ ${\displaystyle (D/N)=(-43/167)=1}$ ${\displaystyle 4\cdot (167)=25^{2}+(43)(1^{2})}$

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

En este caso, m = 143 = 11×13. Desafortunadamente, no podemos elegir 11 o 13 como nuestro q , ya que no satisface la desigualdad necesaria. Sin embargo, nos salva una proposición análoga a la que enunciamos antes del algoritmo de Goldwasser-Kilian, que proviene de un artículo de Morain. ^[13] Establece que, dado nuestro m , buscamos un s que divida a m , , pero que no sea necesariamente primo, y verificamos si, para cada uno que divida a s ${\displaystyle s>(N^{1/4}+1)^{2}}$ ${\displaystyle p_{i}}$

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

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

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

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

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

Pero antes de poder hacer esto, debemos construir nuestra curva y elegir un punto P. Para construir la curva, utilizamos la multiplicación compleja. En nuestro caso, calculamos la invariante J.

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

A continuación calculamos

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

y sabemos que nuestra curva elíptica tiene 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 . Así que podemos empezar con ${\displaystyle \mathbb {F} _{167}}$

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

que produce

${\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 11 P = (140, 147), y por tanto, por la proposición de Morain, N es primo.

Complejidad y tiempos de ejecución

El algoritmo de demostración de primalidad de curva elíptica de Goldwasser y Kilian termina en el tiempo polinomial esperado durante al menos

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

de insumos primarios.

Conjetura

Sea el número de primos menores que x ${\displaystyle \pi (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 Goldwasser-Kilian termina en el tiempo polinomial esperado para cada entrada. Además, si nuestra N tiene una longitud k , entonces el algoritmo crea un certificado de tamaño que puede verificarse en . ^[14] ${\displaystyle O(k^{2})}$ ${\displaystyle O(k^{4})}$

Consideremos ahora otra conjetura, que nos dará un límite para el tiempo total del algoritmo.

Conjetura 2

Supongamos que existen constantes positivas y tales que la cantidad de primos en el intervalo ${\displaystyle c_{1}}$ ${\displaystyle c_{2}}$

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

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

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

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

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

Primos de forma especial

Para algunas formas de números, es posible encontrar "atajos" para una prueba de primalidad. Este es el caso de los números de Mersenne . De hecho, debido a su estructura especial, que permite una verificación más fácil de la primalidad, los seis números primos más grandes conocidos son todos números de Mersenne. ^[15] Existe un método en uso desde hace algún tiempo para verificar la primalidad de los números de Mersenne, conocido como la prueba de Lucas-Lehmer . Esta prueba no se basa en curvas elípticas. Sin embargo, presentamos un resultado donde los números de la forma donde , n impares pueden demostrarse primos (o compuestos) utilizando curvas elípticas. Por supuesto, esto también proporcionará un método para demostrar la primalidad de los números de Mersenne, que corresponden al caso donde n = 1. El siguiente método se extrae del artículo Primality Test for using Elliptic Curves , de Yu Tsumura. ^[16] ${\displaystyle N=2^{k}n-1}$ ${\displaystyle k,n\in \mathbb {Z} ,k\geq 2}$ ${\displaystyle 2^{k}n-1}$

Estructura del grupomi(Fnorte)

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

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

Teorema 2. o dependiendo de si m es o no un residuo cuadrático módulo p . ${\displaystyle E(\mathbb {F} _{p})\cong \mathbb {Z} _{2^{k}n}}$ ${\displaystyle E(\mathbb {F} _{p})\cong \mathbb {Z} _{2}\oplus \mathbb {Z} _{2^{k-1}n}}$

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

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

Teorema 4. Elija a y suponga ${\displaystyle \lambda >1}$

${\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 sólo si existe un Q = ( x , y ) en E , tal que para i = 1, 2, ..., k  − 1 y donde es una secuencia con valor inicial . ${\displaystyle \gcd {(S_{i},p)}=1}$ ${\displaystyle S_{k}\equiv 0{\pmod {p}},}$ ${\displaystyle S_{i}}$ ${\displaystyle S_{0}=x}$

El algoritmo

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

(1) Elija tal que , y encuentre tal que . ${\displaystyle x\in \mathbb {Z} }$ ${\displaystyle \left({\frac {x}{N}}\right)=-1}$ ${\displaystyle y\in \mathbb {Z} ,y\not \equiv 0{\pmod {2}}}$ ${\displaystyle \left({\frac {x^{3}-y^{2}}{N}}\right)=1}$

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

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

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

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

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

(3) Si entonces es primo. En caso contrario, es compuesto. Con esto se completa la prueba. ${\displaystyle S_{k}\equiv 0{\pmod {N}}}$ ${\displaystyle N}$ ${\displaystyle N}$

Justificación del algoritmo

En (1), se elige una curva elíptica, E , junto con un punto Q en E , de modo que la coordenada x de Q sea un residuo cuadrático no residual. Podemos decir

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

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

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

También existe un algoritmo para cuando n es grande; sin embargo, para esto nos remitimos al artículo mencionado anteriormente. ^[16]

Referencias

1. Henri Cohen, Gerhard Frey, ed. (2006). Manual de criptografía de curvas elípticas e hiperelípticas . Boca Raton: Chapman & Hall/CRC.
2. Top, Jaap, Demostración de la primalidad de la curva elíptica , http://www.math.rug.nl/~top/atkin.pdf
3. Atkin, AOL; Morain, F. (1993). "Curvas elípticas y demostración de primalidad". Matemáticas de la computación . 61 (203): 29–68. doi : 10.2307/2152935 . JSTOR  2152935.
4. Lenstra, Alaska; Lenstra, HW (1990). "Algoritmos en teoría de números". Algoritmos y Complejidad (PDF) . págs. 673–715. doi :10.1016/B978-0-444-88071-0.50017-5. ISBN 9780444880710.
5. Caldwell, Chris. Los veinte mejores: prueba de primalidad de curva elíptica a partir de las páginas de primos .
6. Samuel S. Wagstaff Jr. (2013). El placer de factorizar. Providence, RI: American Mathematical Society. págs. 187-188. ISBN 978-1-4704-1048-3.
7. Washington, Lawrence C. , Curvas elípticas: teoría de números y criptografía , Chapman & Hall/CRC, 2003
8. Koblitz, Neal, Introducción a la teoría de números y criptografía , 2.ª edición, Springer, 1994
9. "Queen's University Canada" (PDF) . Archivado desde el original (PDF) el 4 de marzo de 2016. Consultado el 22 de enero de 2010 .
10. Blake, I.; Seroussi, G.; Smart, N. (1999). Curvas elípticas en criptografía . doi :10.1017/CBO9781107360211. ISBN 9780521653749.
11. Lenstra, Hendrik W., Algoritmos eficientes en teoría de números , https://openaccess.leidenuniv.nl/bitstream/1887/2141/1/346_081.pdf
12. El ECPP vuelve a estar disponible en algo.inria.fr
13. Morain, F. (1988). "Implementación del algoritmo de prueba de primalidad Atkin-Goldwasser-Kilian" (PDF) . S2CID  118191463.
14. Goldwasser, Shafi, Kilian, Joe, Casi todos los Primes pueden certificarse rápidamente , http://www.iai.uni-bonn.de/~adrian/ecpp/p316-goldwasser.pdf Archivado el 18 de julio de 2011 en Wayback Machine.
15. "El mayor número primo conocido por año: una breve historia".
16. Tsumura, Yu (2009). "Pruebas de primalidad para el uso de curvas elípticas". arXiv : 0912.5279v1 [math.NT]. ${\displaystyle 2^{k}n-1}$

Enlaces externos

• Curvas elípticas y demostración de primalidad por Atkin y Morain.
• Weisstein, Eric W. "Demostración de la primalidad de la curva elíptica". MathWorld .
• Chris Caldwell, "Demostración de primalidad 4.2: curvas elípticas y la prueba ECPP" en Prime Pages .
• François Morain, "La página de inicio de ECPP" (incluye software ECPP antiguo para algunas arquitecturas).
• Marcel Martin, "Primo" (binario para Linux de 64 bits)
• PARI/GP, un sistema de álgebra computacional con funciones para crear certificados de primalidad de Atkin-Morain y Primo
• GMP-ECPP, una implementación libre de ECPP
• LiDIA, una biblioteca C++ gratuita para Linux con soporte ECPP
• CM, otra biblioteca gratuita que contiene una implementación de ECPP