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 prueba de primalidad de curva elíptica (ECPP), se encuentran entre los métodos más rápidos y más utilizados en la prueba de primalidad. ^[1] Es una idea propuesta por Shafi Goldwasser y Joe Kilian en 1986 y convertida en algoritmo por AOL Atkin el mismo año. El algoritmo fue modificado y mejorado posteriormente por varios colaboradores, y en particular por Atkin y François Morain  [de] , en 1993. ^[2] El concepto de uso de curvas elípticas en la factorización había sido desarrollado por HW Lenstra en 1985, y las implicaciones para su Su uso en pruebas (y pruebas) de primalidad siguió rápidamente.

Las pruebas de primalidad son un campo que ha existido desde la época de Fermat , en cuya época la mayoría de los algoritmos se basaban en la factorización, que se vuelve difícil de manejar con grandes entradas ^{[ ancla rota ]} ; Los algoritmos modernos tratan por separado los problemas de determinar si un número es primo y cuáles son sus factores. Adquirió importancia práctica con la llegada de la criptografía moderna. Aunque muchas pruebas actuales dan como resultado un resultado probabilístico ( 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 una rápida certificado comprobable. ^[3]

Los métodos de prueba de primos previamente conocidos, 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 requirieron algo de suerte y, en general, son lentos en la práctica. ${\displaystyle N\pm 1}$ ${\displaystyle N}$

Prueba de primalidad de la 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 se desconoce 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 en algunas versiones mediante argumentos heurísticos. ECPP funciona de la misma manera que la mayoría de las otras pruebas de primalidad : encontrar un grupo y mostrar que su tamaño es primo. Para ECPP, el grupo es una curva elíptica sobre un conjunto finito de formas cuadráticas, de modo que es trivial factorizar el grupo. ${\displaystyle \varepsilon >0}$ ${\displaystyle 4+\varepsilon }$ ${\displaystyle p}$ ${\displaystyle p-1}$

ECPP genera un certificado de primalidad de Atkin – Goldwasser –Kilian–Morain por recursividad y luego intenta verificar el certificado. El paso que requiere 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 comprobar el funcionamiento en muy poco tiempo.

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

Proposición

Las pruebas de primalidad de la curva elíptica se basan en criterios análogos al criterio de Pocklington, en el que se basa esa prueba, ^{[6] [7]} donde el grupo se reemplaza por y E es una curva elíptica adecuadamente elegida. Ahora expondremos 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 la curva elíptica. ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{*}}$ ${\displaystyle E(\mathbb {Z} /n\mathbb {Z} ),}$

Sea N un número entero positivo y E el conjunto definido por la ecuación. Considere E en lugar de utilizar la ley de suma 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 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 ${\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. Definir como la curva elíptica definida por la misma ecuación que E pero evaluada en módulo  p en lugar de  módulo N. Definir como el orden del grupo . Por el teorema de Hasse sobre las 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 existe un número entero u con la propiedad de que ${\displaystyle \gcd(q,m_{p})=1}$

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

Sea el punto P evaluado módulo p . Así, 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 usando 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 producirá: ^[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 número entero, N , es primo. Esto se hace de la siguiente manera: ^[6]

Elija tres números enteros al azar, a, x, y y establezca

${\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 indefinida , 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. En caso contrario, descartamos nuestra curva y seleccionamos aleatoriamente otra tripleta (a, x, y) para empezar de nuevo. La idea aquí es encontrar una 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, proceda a calcular mP y kP . Si alguno de los dos cálculos produce una expresión indefinida, podemos obtener un factor no trivial de N. Si ambos cálculos tienen éxito, examinamos los resultados.

Si está claro que N no es primo, porque si N fuera primo entonces E tendría orden m , y cualquier elemento de E pasaría a ser 0 al multiplicarse por m . Si kP = 0, entonces el algoritmo descarta E y comienza de nuevo con un triple a, x, y diferente . ${\displaystyle mP\neq 0}$

Ahora, si y entonces nuestra proposición anterior nos dice 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 hemos descrito un algoritmo 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 algún umbral en el que 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 en E usando 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 realizadas por 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 antes. No existe ningún teorema conocido que garantice que podamos encontrar una E adecuada en muchos intentos polinómicos. No es lo mismo la distribución de primos en el intervalo de Hasse , que contiene m , que la distribución de primos en los órdenes de grupo, contando curvas con multiplicidad. Sin embargo, esto no es un problema importante en la práctica. ^[8] ${\displaystyle [p+1-2{\sqrt {p}},p+1+2{\sqrt {p}}]}$

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 (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 sea fácil de calcular. La multiplicación compleja es clave en la construcción de la curva.

Ahora, dado un N para el cual es necesario demostrar la primalidad, necesitamos encontrar m y 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. )

ECPP utiliza una multiplicación compleja para construir la curva E , y lo hace de una manera que permite calcular fácilmente m (el número de puntos en E ). Ahora describiremos este método:

La utilización de la multiplicación compleja requiere un discriminante negativo , D , tal que D puede 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 divida en dos elementos, lo necesitamos (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 creciente ( D ). Para cada D , verifique si 4 N se puede escribir 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 hayan descubierto D y a aceptables , calcule . Ahora si m tiene un factor primo q de tamaño ${\displaystyle m=N+1-a}$

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

Usa el método de multiplicación complejo para construir la curva E y un punto P en ella. Entonces podemos usar nuestra proposición para verificar la primalidad de N . Tenga en cuenta que si m no tiene un factor primo grande o no puede factorizarse con la suficiente rapidez, se puede elegir otra opción de D. ^[1]

Método de multiplicación complejo

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 se puede escribir como un producto de dos elementos).

Supongamos primero eso y (estos casos se resuelven mucho más fácilmente). Es necesario calcular los j-invariantes elípticos de las clases h ( D ) del orden del discriminante D como números complejos . Existen varias fórmulas para calcularlos. ${\displaystyle D\neq -3}$ ${\displaystyle D\neq -4}$

A continuación, cree el polinomio mónico , que tiene raíces correspondientes a los valores de h ( D ). Tenga en cuenta que ese 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 suficiente precisión para descubrir sus valores verdaderos. ${\displaystyle H_{D}(X)}$ ${\displaystyle H_{D}(X)}$ ${\displaystyle H_{D}(X)}$

Ahora, si N es primo, CM nos dice que divide el módulo  N en un producto de h ( D ) factores lineales, basándose en el hecho de que D se eligió de modo que N se divida como producto de dos elementos. Ahora bien, si j es una de las raíces h ( D ) 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 mod cuadrático sin residuos N y r es 0 o 1.

Dada una raíz j sólo hay dos posibles elecciones no isomorfas de E , una para cada elecció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 de Goldwasser-Killian, ésta conduce a un procedimiento de reducción. Nuevamente el culpable es q . Una vez que encontramos una q que funciona, debemos verificar que sea prima, por lo que, de hecho, ahora estamos haciendo toda la prueba para q . Por otra parte, 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 , an my 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 pueden escribir como . ${\displaystyle N=167}$ ${\displaystyle (D/N)=1}$ ${\displaystyle 4N=a^{2}+|D|b^{2}}$

Para nuestro ejemplo se elige. Esto se debe a que y además, usando el algoritmo de Cornacchia , sabemos que y por 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, lo que produce. A continuación, necesitamos encontrar un divisor primo probable de m , al que se hace referencia como 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 nuestra q , ya que no satisface la desigualdad necesaria. Nos salva, sin embargo, una proposición análoga a la que enunciamos antes del algoritmo Goldwasser-Kilian, que proviene de un artículo de Morain. ^[13] Afirma que dado nuestro m , buscamos un s que divida a m , pero no es necesariamente primo, y verificamos si, para cada uno que divide 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 que podamos hacer esto, debemos construir nuestra curva y elegir un punto P. Para construir la curva utilizamos la multiplicación compleja. En nuestro caso calculamos el J-invariante

${\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 cuadrado en . Entonces podemos comenzar con ${\displaystyle \mathbb {F} _{167}}$

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

cuyos rendimientos

${\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), por lo que, según la proposición de Morain, N es primo.

Complejidad y tiempos de ejecución.

El algoritmo de prueba de primalidad de curva elíptica de Goldwasser y Kilian termina en el tiempo polinómico esperado durante al menos

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

de insumos primos.

Conjetura

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

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

Conjetura 2

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

${\displaystyle [x,x+{\sqrt {2x}}],x\geq 2}$ Es mas 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 sencilla de la primalidad, los seis números primos más grandes conocidos son todos números de Mersenne. ^[15] Desde hace algún tiempo se utiliza un método para verificar la primalidad de los números de Mersenne, conocido como prueba de Lucas-Lehmer . Esta prueba no se basa en curvas elípticas. Sin embargo, presentamos un resultado donde se puede demostrar que los números de la forma donde , n impar son primos (o compuestos) usando 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 en el que n = 1. El siguiente método está extraído del artículo Prueba de primalidad para usar curvas elípticas , de Yu Tsumura. ^[dieciséis] ${\displaystyle N=2^{k}n-1}$ ${\displaystyle k,n\in \mathbb {Z} ,k\geq 2}$ ${\displaystyle 2^{k}n-1}$

Estructura del grupo demi(Fnorte)

Tomamos E como nuestra curva elíptica, donde E tiene la forma de 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 módulo de residuo cuadrático 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 sea un módulo cuadrático sin residuos 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 determinado , 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}$

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

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

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

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

Si es para an , donde entonces es compuesto. De lo contrario, continúe con (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. Esto 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 no residuo cuadrático. 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.}$

Por tanto, si N es primo, Q' tiene orden divisible por , por el Teorema 3 y, por 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, realmente es compuesto. (2) y (3) comprobar 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, por lo que N es verdaderamente primo. ${\displaystyle S_{1}}$

También existe un algoritmo para cuando n es grande; sin embargo, para ello nos remitimos al artículo antes mencionado. ^[dieciséis]

Referencias

1. Henri Cohen, Gerhard Frey, ed. (2006). Manual de criptografía de curvas elípticas e hiperelípticas . Boca Ratón: Chapman & Hall/CRC.
2. Arriba, Jaap, Prueba de primalidad de 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 primeros: prueba de primalidad de la curva elíptica de las páginas principales ".
6. Samuel S. Wagstaff Jr. (2013). El placer del factoraje. Providence, RI: Sociedad Estadounidense de Matemáticas. 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 la criptografía , 2.ª edición, Springer, 1994
9. "Queen's University Canadá" (PDF) . Archivado desde el original (PDF) el 4 de marzo de 2016 . Consultado el 22 de enero de 2010 .
10. Blake, yo.; Seroussi, G.; Inteligente, 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. ECPP regresa 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 números primos se pueden certificar rápidamente , http://www.iai.uni-bonn.de/~adrian/ecpp/p316-goldwasser.pdf Archivado el 18 de julio de 2011 en Wayback. Máquina
15. "El primo más grande conocido por año: una breve historia".
16. Tsumura, Yu (2009). "Pruebas de primalidad para el uso de curvas elípticas". arXiv : 0912.5279v1 [matemáticas.NT]. ${\displaystyle 2^{k}n-1}$

enlaces externos

• Curvas elípticas y demostración de primalidad de Atkin y Morain.
• Weisstein, Eric W. "Demostración de primalidad de curva elíptica". MundoMatemático .
• Chris Caldwell, "Primality Proving 4.2: curvas elípticas y 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 informática con funciones para crear certificados de primalidad Atkin-Morain y Primo
• GMP-ECPP, una implementación ECPP gratuita
• LiDIA, una biblioteca C++ gratuita para Linux con soporte ECPP
• CM, otra biblioteca gratuita que contiene una implementación ECPP