Factorización de curva elíptica de Lenstra

Algoritmo de factorización de números enteros

La factorización de curva elíptica de Lenstra o el método de factorización de curva elíptica ( ECM ) es un algoritmo de tiempo de ejecución subexponencial rápido para la factorización de enteros , que emplea curvas elípticas . Para la factorización de propósito general , ECM es el tercer método de factorización más rápido conocido. El segundo más rápido es el tamiz cuadrático polinomial múltiple y el más rápido es el tamiz de campo numérico general . La factorización de curva elíptica de Lenstra lleva el nombre de Hendrik Lenstra .

En la práctica, ECM se considera un algoritmo de factorización de propósito especial, ya que es más adecuado para encontrar factores pequeños. Actualmente ^[actualizar], sigue siendo el mejor algoritmo para divisores que no exceden de 50 a 60 dígitos , ya que su tiempo de ejecución está dominado por el tamaño del factor más pequeño p en lugar del tamaño del número n a factorizar. Con frecuencia, ECM se utiliza para eliminar factores pequeños de un número entero muy grande con muchos factores; si el número entero restante sigue siendo compuesto, entonces sólo tiene factores grandes y se factoriza utilizando técnicas de propósito general. El factor más grande encontrado utilizando ECM hasta el momento tiene 83 dígitos decimales y fue descubierto el 7 de septiembre de 2013 por R. Propper. ^[1] Aumentar el número de curvas probadas mejora las posibilidades de encontrar un factor, pero no son lineales con el aumento del número de dígitos.

Algoritmo

El método de factorización de curva elíptica de Lenstra para encontrar un factor de un número natural determinado funciona de la siguiente manera: ${\displaystyle n}$

1. Elija una curva elíptica aleatoria (los números enteros módulo ), con una ecuación de la forma junto con un punto no trivial en ella. ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$ ${\displaystyle n}$ ${\displaystyle y^{2}=x^{3}+ax+b{\pmod {n}}}$ ${\displaystyle P(x_{0},y_{0})}$

   Esto se puede hacer seleccionando primero random y luego configurándolo para asegurar que el punto esté en la curva. ${\displaystyle x_{0},y_{0},a\in \mathbb {Z} /n\mathbb {Z} }$ ${\displaystyle b=y_{0}^{2}-x_{0}^{3}-ax_{0}{\pmod {n}}}$

2. Se puede definir Suma de dos puntos en la curva, para definir un grupo . Las leyes de la suma se dan en el artículo sobre curvas elípticas .

   Podemos formar múltiplos repetidos de un punto : . Las fórmulas de suma implican tomar la pendiente modular de una unión de cuerdas y , por lo tanto, dividir el módulo entre clases de residuos , realizado utilizando el algoritmo euclidiano extendido . En particular, la división por algunos incluye el cálculo de . ${\displaystyle P}$ ${\displaystyle [k]P=P+\ldots +P{\text{ (k times)}}}$ ${\displaystyle P}$ ${\displaystyle Q}$ ${\displaystyle n}$ ${\displaystyle v{\bmod {n}}}$ ${\displaystyle \gcd(v,n)}$

   Suponiendo que calculamos una pendiente de la forma con , entonces si , el resultado de la suma de puntos será , el punto "en el infinito" correspondiente a la intersección de la línea "vertical" que une y la curva. Sin embargo, si , entonces la suma de puntos no producirá un punto significativo en la curva; pero, lo que es más importante, es un factor no trivial de . ${\displaystyle u/v}$ ${\displaystyle \gcd(u,v)=1}$ ${\displaystyle v=0{\bmod {n}}}$ ${\displaystyle \infty }$ ${\displaystyle P(x,y),P'(x,-y)}$ ${\displaystyle \gcd(v,n)\neq 1,n}$ ${\displaystyle \gcd(v,n)}$ ${\displaystyle n}$

3. Calcule sobre la curva elíptica ( ), donde es un producto de muchos números pequeños: digamos, un producto de números primos pequeños elevados a potencias pequeñas, como en el algoritmo p-1 , o el factorial para algunos no demasiado grandes . Esto se puede hacer de manera eficiente, un pequeño factor a la vez. Digamos que para obtener , primero calcule , luego , luego , y así sucesivamente. se elige para que sea lo suficientemente pequeño como para que la suma de puntos inteligentes se pueda realizar en un tiempo razonable. ${\displaystyle [k]P}$ ${\displaystyle {\bmod {n}}}$ ${\displaystyle k}$ ${\displaystyle B!}$ ${\displaystyle B}$ ${\displaystyle [B!]P}$ ${\displaystyle [2]P}$ ${\displaystyle [3]([2]P)}$ ${\displaystyle [4]([3!]P)}$ ${\displaystyle B}$ ${\displaystyle B}$
   • Si terminamos todos los cálculos anteriores sin encontrar elementos no invertibles ( ), significa que el orden de las curvas elípticas (módulo primos) no es lo suficientemente suave , por lo que debemos intentarlo nuevamente con una curva y un punto de partida diferentes. ${\displaystyle {\bmod {n}}}$
   • Si encontramos a hemos terminado: es un factor no trivial de . ${\displaystyle \gcd(v,n)\neq 1,n}$ ${\displaystyle n}$

La complejidad temporal depende del tamaño del factor primo más pequeño del número y se puede representar mediante exp[( √ 2  +  o (1)) √ ln  p  ln ln  p ] , donde p es el factor más pequeño de n , o , en L -notación . ${\displaystyle L_{p}\left[{\frac {1}{2}},{\sqrt {2}}\right]}$

Explicación

Si p y q son dos divisores primos de n , entonces y ²  =  x ³  + ax  +  b  (mod  n ) implica la misma ecuación también módulo  p y módulo  q . Estas dos curvas elípticas más pequeñas con la suma son ahora grupos genuinos . Si estos grupos tienen N _p y N _q elementos, respectivamente, entonces para cualquier punto P en la curva original, según el teorema de Lagrange , k  > 0 es mínimo tal que en la curva el módulo p implica que k divide a N _p ; además, . La afirmación análoga es válida para la curva módulo q . Cuando la curva elíptica se elige al azar, entonces N _p y N _q son números aleatorios cercanos a p  + 1 y q  + 1, respectivamente (ver más abajo). Por lo tanto, es poco probable que la mayoría de los factores primos de N _p y N _q sean iguales, y es muy probable que al calcular eP , encontremos algún kP que sea ∞ módulo  p pero no módulo  q , o viceversa. Cuando este es el caso, kP no existe en la curva original, y en los cálculos encontramos algo de v con mcd( v , p ) =  p o mcd( v ,  q ) =  q , pero no con ambos. Es decir, mcd( v ,  n ) dio un factor no trivial de  n . ${\displaystyle \boxplus }$ ${\displaystyle kP=\infty }$ ${\displaystyle N_{p}P=\infty }$

ECM es, en esencia, una mejora del antiguo algoritmo p  -1 . El algoritmo p  − 1 encuentra factores primos p tales que p  − 1 es b-powersmooth para valores pequeños de b . Para cualquier e , múltiplo de p  − 1, y cualquier a relativamente primo de p , según el pequeño teorema de Fermat tenemos a ^e  ≡ 1 ( mod p ) . Entonces es probable que mcd ( a ^e  − 1,  n ) produzca un factor de n . Sin embargo, el algoritmo falla cuando p  - 1 tiene factores primos grandes, como es el caso de los números que contienen primos fuertes , por ejemplo.

ECM sortea este obstáculo considerando el grupo de una curva elíptica aleatoria sobre el campo finito Z _p , en lugar de considerar el grupo multiplicativo de Z _p que siempre tiene orden  p  − 1.

El orden del grupo de una curva elíptica sobre Z _p varía (bastante aleatoriamente) entre p  + 1 − 2 √ p y p  + 1 + 2 √ p según el teorema de Hasse , y es probable que sea suave para algunas curvas elípticas. Aunque no hay pruebas de que se encuentre un orden de grupo fluido en el intervalo de Hasse, utilizando métodos probabilísticos heurísticos , el teorema de Canfield-Erdős-Pomerance con elecciones de parámetros adecuadamente optimizadas y la notación L , podemos esperar probar L [ √ 2 /2, √ 2 ] curvas antes de obtener un orden de grupo suave. Esta estimación heurística es muy fiable en la práctica.

Uso de ejemplo

El siguiente ejemplo es de Trappe y Washington (2006), con algunos detalles agregados.

Queremos factorizar n = 455839. Elijamos la curva elíptica y ² = x ³ + 5 x – 5, con el punto P = (1, 1) en ella, e intentemos calcular (10 ! ) P.

La pendiente de la recta tangente en algún punto A =( x , y ) es s = (3 x ² + 5)/(2 y ) (mod n) . Usando s podemos calcular 2 A . Si el valor de s es de la forma a/b donde b > 1 y mcd( a , b ) = 1, tenemos que encontrar el inverso modular de b . Si no existe, mcd( n , b ) es un factor no trivial de n .

Primero calculamos 2 P . Tenemos s ( P ) = s (1,1) = 4, por lo que las coordenadas de 2 P = ( x ′ , y ′ ) son x ′ = s ² – 2 x = 14 y y ′ = s ( x – x ′ ) – y = 4(1 – 14) – 1 = –53, todos los números entendidos (mod n ). Sólo para comprobar que este 2 P está efectivamente en la curva: (–53) ² = 2809 = 14 ³ + 5·14 – 5.

Luego calculamos 3(2 P ). Tenemos s (2 P ) = s (14,-53) = –593/106 (mod n ). Usando el algoritmo euclidiano : 455839 = 4300·106 + 39, luego 106 = 2·39 + 28, luego 39 = 28 + 11, luego 28 = 2·11 + 6, luego 11 = 6 + 5, luego 6 = 5 + 1. Por lo tanto, mcd(455839, 106) = 1, y trabajando hacia atrás (una versión del algoritmo euclidiano extendido ): 1 = 6 – 5 = 2·6 – 11 = 2·28 – 5·11 = 7·28 – 5 ·39 = 7·106 – 19·39 = 81707·106 – 19·455839. Por tanto, 106 ⁻¹ = 81707 (mod 455839) y –593/106 = –133317 (mod 455839). Dado este s , podemos calcular las coordenadas de 2(2 P ), tal como lo hicimos anteriormente: 4 P = (259851, 116255). Sólo para comprobar que efectivamente se trata de un punto de la curva: y ² = 54514 = x ³ + 5 x – 5 (mod 455839). Después de esto, podemos calcular . ${\displaystyle 3(2P)=4P\boxplus 2P}$

¡Podemos calcular de manera similar 4! P , y así sucesivamente, ¡pero 8! P requiere invertir 599 (mod 455839). El algoritmo euclidiano da que 455839 es divisible por 599, y hemos encontrado una factorización 455839 = 599·761.

La razón por la que esto funcionó es que la curva (mod 599) tiene 640 = 2 ⁷ ·5 puntos, mientras que (mod 761) tiene 777 = 3,7 ·37 puntos. Además, 640 y 777 son los enteros positivos más pequeños k tales que kP = ∞ en la curva (mod 599) y (mod 761), respectivamente. ¡Desde las 8! es múltiplo de 640 pero no múltiplo de 777, ¡tenemos 8! P = ∞ en la curva (mod 599), pero no en la curva (mod 761), por lo tanto, la suma repetida se descompuso aquí, lo que produjo la factorización.

El algoritmo con coordenadas proyectivas.

Antes de considerar el plano proyectivo, considere primero un espacio proyectivo "normal" : en lugar de puntos, se estudian líneas que pasan por el origen. Una línea puede representarse como un punto distinto de cero , bajo una relación de equivalencia ~ dada por: ⇔ ∃ c ≠ 0 tal que x' = c x , y' = c y y z' = c z . Bajo esta relación de equivalencia, el espacio se llama plano proyectivo ; Los puntos, denotados por , corresponden a líneas en un espacio tridimensional que pasan por el origen. Tenga en cuenta que el punto no existe en este espacio ya que para dibujar una línea en cualquier dirección posible se requiere al menos uno de x',y' o z' ≠ 0. Ahora observe que casi todas las líneas pasan por cualquier plano de referencia dado, como el plano ( X , Y ,1), mientras que las líneas precisamente paralelas a este plano, que tienen coordenadas ( X,Y ,0), especifican direcciones de forma única, como 'puntos en el infinito' que se utilizan en el plano afín ( X,Y )-plano sobre el que se encuentra. ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )/\sim ,}$ ${\displaystyle \mathbb {R} }$ ${\displaystyle (x,y,z)}$ ${\displaystyle (x,y,z)\sim (x',y',z')}$ ${\displaystyle \mathbb {P} ^{2}}$ ${\displaystyle (x:y:z)}$ ${\displaystyle (0:0:0)}$

En el algoritmo sólo se utiliza la estructura de grupo de una curva elíptica sobre el campo. Como no necesariamente necesitamos el campo , un campo finito también proporcionará una estructura de grupo en una curva elíptica. Sin embargo, considerando la misma curva y la operación con n no primo no se obtiene un grupo. El método de la curva elíptica utiliza los casos de fallo de la ley de la suma. ${\displaystyle \mathbb {R} }$ ${\displaystyle \mathbb {R} }$ ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )/\sim }$

Ahora expresamos el algoritmo en coordenadas proyectivas. El elemento neutro viene dado entonces por el punto en el infinito . Sea n un número entero (positivo) y considere la curva elíptica (un conjunto de puntos con alguna estructura) . ${\displaystyle (0:1:0)}$ ${\displaystyle E(\mathbb {Z} /n\mathbb {Z} )=\{(x:y:z)\in \mathbb {P} ^{2}\ |\ y^{2}z=x^{3}+axz^{2}+bz^{3}\}}$

1. Elija con un ≠ 0. ${\displaystyle x_{P},y_{P},a\in \mathbb {Z} /n\mathbb {Z} }$
2. Calcular . La curva elíptica E está entonces en la forma de Weierstrass dada por y mediante el uso de coordenadas proyectivas la curva elíptica está dada por la ecuación homogénea . Tiene el punto . ${\displaystyle b=y_{P}^{2}-x_{P}^{3}-ax_{P}}$ ${\displaystyle y^{2}=x^{3}+ax+b}$ ${\displaystyle ZY^{2}=X^{3}+aZ^{2}X+bZ^{3}}$ ${\displaystyle P=(x_{P}:y_{P}:1)}$
3. Elija un límite superior para esta curva elíptica. Observación: Solo encontrará factores p si el orden de grupo de la curva elíptica E sobre ( denotada por ) es B-suave , lo que significa que todos los factores primos de tienen que ser menores o iguales a B. ${\displaystyle B\in \mathbb {Z} }$ ${\displaystyle \mathbb {Z} /p\mathbb {Z} }$ ${\displaystyle \#E(\mathbb {Z} /p\mathbb {Z} )}$ ${\displaystyle \#E(\mathbb {Z} /p\mathbb {Z} )}$
4. Calcular . ${\displaystyle k={\rm {lcm}}(1,\dots ,B)}$
5. Calcula ( k veces) en el anillo . Tenga en cuenta que si es B -suave y n es primo (y por lo tanto es un campo), eso . Sin embargo, si solo B es suave para algún divisor p de n , el producto podría no ser (0:1:0) porque la suma y la multiplicación no están bien definidas si n no es primo. En este caso, se puede encontrar un divisor no trivial. ${\displaystyle kP:=P+P+\cdots +P}$ ${\displaystyle E(\mathbb {Z} /n\mathbb {Z} )}$ ${\displaystyle \#E(\mathbb {Z} /n\mathbb {Z} )}$ ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$ ${\displaystyle kP=(0:1:0)}$ ${\displaystyle \#E(\mathbb {Z} /p\mathbb {Z} )}$
6. De lo contrario, regrese al paso 2. Si esto ocurre, lo notará al simplificar el producto. ${\displaystyle kP.}$

En el punto 5 se dice que, en las circunstancias adecuadas, se puede encontrar un divisor no trivial. Como se señala en el artículo de Lenstra (Factoring Integers with Elliptic Curves), la suma necesita la suposición . Si no son y distintos (de lo contrario, la suma funciona de manera similar, pero es un poco diferente), entonces la suma funciona de la siguiente manera: ${\displaystyle \gcd(x_{1}-x_{2},n)=1}$ ${\displaystyle P,Q}$ ${\displaystyle (0:1:0)}$

• Calcular: , ${\displaystyle R=P+Q;}$ ${\displaystyle P=(x_{1}:y_{1}:1),Q=(x_{2}:y_{2}:1)}$
• ${\displaystyle \lambda =(y_{1}-y_{2})(x_{1}-x_{2})^{-1}}$,
• ${\displaystyle x_{3}=\lambda ^{2}-x_{1}-x_{2}}$,
• ${\displaystyle y_{3}=\lambda (x_{1}-x_{3})-y_{1}}$,
• ${\displaystyle R=P+Q=(x_{3}:y_{3}:1)}$.

Si la suma falla, esto se deberá a un fallo en el cálculo. En particular, porque no siempre se puede calcular si n no es primo (y por tanto no es un campo). Sin hacer uso de ser campo, se podría calcular: ${\displaystyle \lambda .}$ ${\displaystyle (x_{1}-x_{2})^{-1}}$ ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$ ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$

• ${\displaystyle \lambda '=y_{1}-y_{2}}$,
• ${\displaystyle x_{3}'={\lambda '}^{2}-x_{1}(x_{1}-x_{2})^{2}-x_{2}(x_{1}-x_{2})^{2}}$,
• ${\displaystyle y_{3}'=\lambda '(x_{1}(x_{1}-x_{2})^{2}-x_{3}')-y_{1}(x_{1}-x_{2})^{3}}$,
• ${\displaystyle R=P+Q=(x_{3}'(x_{1}-x_{2}):y_{3}':(x_{1}-x_{2})^{3})}$y simplificar si es posible.

Este cálculo siempre es legal y si el mcd de la coordenada Z es n ≠ (1 o n ), cuando la simplificación falla, se encuentra un divisor no trivial de n .

Curvas retorcidas de Edwards

El uso de curvas de Edwards necesita menos multiplicaciones modulares y menos tiempo que el uso de curvas de Montgomery o curvas de Weierstrass (otros métodos utilizados). Usando las curvas de Edwards también puedes encontrar más números primos.

Definición. Sea un campo en el que y sea con . Entonces la curva de Edwards torcida está dada por Una curva de Edwards es una curva de Edwards torcida en la que . ${\displaystyle k}$ ${\displaystyle 2\neq 0}$ ${\displaystyle a,d\in k\setminus \{0\}}$ ${\displaystyle a\neq d}$ ${\displaystyle E_{E,a,d}}$ ${\displaystyle ax^{2}+y^{2}=1+dx^{2}y^{2}.}$ ${\displaystyle a=1}$

Hay cinco formas conocidas de construir un conjunto de puntos en una curva de Edwards: el conjunto de puntos afines, el conjunto de puntos proyectivos, el conjunto de puntos invertidos, el conjunto de puntos extendidos y el conjunto de puntos completos.

El conjunto de puntos afines viene dado por:

${\displaystyle \{(x,y)\in \mathbb {A} ^{2}:ax^{2}+y^{2}=1+dx^{2}y^{2}\}}$.

La ley de la suma está dada por

${\displaystyle (e,f),(g,h)\mapsto \left({\frac {eh+fg}{1+degfh}},{\frac {fh-aeg}{1-degfh}}\right).}$

El punto (0,1) es su elemento neutro y el inverso de es . ${\displaystyle (e,f)}$ ${\displaystyle (-e,f)}$

Las otras representaciones se definen de manera similar a cómo la curva proyectiva de Weierstrass se deriva del afín.

Cualquier curva elíptica en forma de Edwards tiene un punto de orden 4. Entonces, el grupo de torsión de una curva de Edwards es isomorfo a o . ${\displaystyle \mathbb {Q} }$ ${\displaystyle \mathbb {Z} /4\mathbb {Z} ,\mathbb {Z} /8\mathbb {Z} ,\mathbb {Z} /12\mathbb {Z} ,\mathbb {Z} /2\mathbb {Z} \times \mathbb {Z} /4\mathbb {Z} }$ ${\displaystyle \mathbb {Z} /2\mathbb {Z} \times \mathbb {Z} /8\mathbb {Z} }$

Los casos más interesantes para ECM son y , ya que obligan a que los órdenes de grupo de la curva módulo primos sean divisibles por 12 y 16 respectivamente. Las siguientes curvas tienen un grupo de torsión isomorfo a : ${\displaystyle \mathbb {Z} /12\mathbb {Z} }$ ${\displaystyle \mathbb {Z} /2\mathbb {Z} \times \mathbb {Z} /8\mathbb {Z} }$ ${\displaystyle \mathbb {Z} /12\mathbb {Z} }$

• ${\displaystyle x^{2}+y^{2}=1+dx^{2}y^{2}}$con punto donde y ${\displaystyle (a,b)}$ ${\displaystyle b\notin \{-2,-1/2,0,\pm 1\},a^{2}=-(b^{2}+2b)}$ ${\displaystyle d=-(2b+1)/(a^{2}b^{2})}$
• ${\displaystyle x^{2}+y^{2}=1+dx^{2}y^{2}}$con punto donde y ${\displaystyle (a,b)}$ ${\displaystyle a={\frac {u^{2}-1}{u^{2}+1}},b=-{\frac {(u-1)^{2}}{u^{2}+1}}}$ ${\displaystyle d={\frac {(u^{2}+1)^{3}(u^{2}-4u+1)}{(u-1)^{6}(u+1)^{2}}},u\notin \{0,\pm 1\}.}$

Cada curva de Edwards con un punto de orden 3 se puede escribir de la manera que se muestra arriba. Las curvas con grupo de torsión isomorfas y pueden ser más eficientes para encontrar números primos. ^[2] ${\displaystyle \mathbb {Z} /2\mathbb {Z} \times \mathbb {Z} /8\mathbb {Z} }$ ${\displaystyle \mathbb {Z} /2\mathbb {Z} \times \mathbb {Z} /4\mathbb {Z} }$

Etapa 2

El texto anterior trata sobre la primera etapa de la factorización de curvas elípticas. Allí se espera encontrar un divisor primo p tal que sea el elemento neutro de . En la segunda etapa se espera haber encontrado un divisor primo q tal que tenga orden primo pequeño en . ${\displaystyle sP}$ ${\displaystyle E(\mathbb {Z} /p\mathbb {Z} )}$ ${\displaystyle sP}$ ${\displaystyle E(\mathbb {Z} /q\mathbb {Z} )}$

Esperamos que el orden esté entre y , donde se determina en la etapa 1 y es el nuevo parámetro de la etapa 2. Se puede verificar un orden pequeño de , calculando el módulo n para cada l primo . ${\displaystyle B_{1}}$ ${\displaystyle B_{2}}$ ${\displaystyle B_{1}}$ ${\displaystyle B_{2}}$ ${\displaystyle sP}$ ${\displaystyle (ls)P}$

GMP-ECM y EECM-MPFQ

^{Bernstein et al [2]} utilizaron el uso de curvas elípticas de Twisted Edwards, así como otras técnicas, para proporcionar una implementación optimizada de ECM. Su único inconveniente es que funciona con números compuestos más pequeños que la implementación de propósito más general, GMP-ECM de Zimmerman.

Método de curva hiperelíptica (HECM)

Hay avances recientes en el uso de curvas hiperelípticas para factorizar números enteros. Cosset muestra en su artículo (de 2010) que se puede construir una curva hiperelíptica de género dos (es decir, una curva con f de grado 5), lo que da el mismo resultado que usar dos curvas elípticas "normales" al mismo tiempo. Al utilizar la superficie de Kummer, el cálculo es más eficiente. Las desventajas de la curva hiperelíptica (frente a una curva elíptica) se compensan con esta forma alternativa de cálculo. Por lo tanto, Cosset afirma aproximadamente que usar curvas hiperelípticas para la factorización no es peor que usar curvas elípticas. ${\displaystyle y^{2}=f(x)}$

Versión cuántica (GEECM)

Bernstein , Heninger , Lou y Valenta sugieren GEECM, una versión cuántica de ECM con curvas de Edwards. ^[3] Utiliza el algoritmo de Grover para aproximadamente duplicar la longitud de los números primos encontrados en comparación con el EECM estándar, asumiendo una computadora cuántica con suficientes qubits y de velocidad comparable a la computadora clásica que ejecuta EECM.

Referencias

1. 50 factores más importantes encontrados por ECM.
2. Berstein, Daniel J.; Birkner, Peter; Lange, Tanja ; Peters, Christiane (9 de enero de 2008). "ECM utilizando curvas de Edwards" (PDF) . Archivo ePrint de criptología .(consulte la parte superior de la página 30 para ver ejemplos de dichas curvas)
3. Bernstein DJ, Heninger N., Lou P., Valenta L. (2017) RSA poscuántica. En: Lange T., Takagi T. (eds), Criptografía poscuántica . PQCrypto 2017. Apuntes de conferencias sobre informática, vol 10346. Springer, Cham

• Bernstein, Daniel J.; Birkner, Peter; Lange, Tanja; Peters, Christiane (2013). "ECM utilizando curvas de Edwards". Matemáticas de la Computación . 82 (282): 1139-1179. doi : 10.1090/S0025-5718-2012-02633-0 . SEÑOR  3008853.
• Bosma, W.; Hulst, MPM van der (1990). Prueba de primalidad con ciclotomía . Doctor. Tesis, Universiteit van Amsterdam. OCLC  256778332.
• Brent, Richard P. (1999). "Factorización del décimo número de Fermat". Matemáticas de la Computación . 68 (225): 429–451. Código Bib : 1999MaCom..68..429B. doi : 10.1090/S0025-5718-99-00992-8 . SEÑOR  1489968.
• Cohen, Henri (1993). Un curso de teoría algebraica computacional de números . Textos de Posgrado en Matemáticas. vol. 138. Berlín: Springer-Verlag. doi :10.1007/978-3-662-02945-9. ISBN 978-0-387-55640-6. SEÑOR  1228206. S2CID  118037646.
• Cosset, R. (2010). "Factorización con curvas de género 2". Matemáticas de la Computación . 79 (270): 1191-1208. arXiv : 0905.2325 . Código Bib : 2010MaCom..79.1191C. doi :10.1090/S0025-5718-09-02295-9. SEÑOR  2600562. S2CID  914296.
• Lenstra, Alaska ; Lenstra Jr., HW, eds. (1993). El desarrollo del tamiz de campo numérico. Apuntes de conferencias de matemáticas. vol. 1554. Berlín: Springer-Verlag. doi :10.1007/BFb0091534. ISBN 978-3-540-57013-4. SEÑOR  1321216.
• Lenstra Jr., HW (1987). "Factorizar números enteros con curvas elípticas" (PDF) . Anales de Matemáticas . 126 (3): 649–673. doi :10.2307/1971363. hdl : 1887/2140 . JSTOR  1971363. SEÑOR  0916721.
• Pomerancia, Carl ; Crandall, Richard (2005). Números primos: una perspectiva computacional (Segunda ed.). Nueva York: Springer. ISBN 978-0-387-25282-7. SEÑOR  2156291.
• Pomerancia, Carl (1985). "El algoritmo de factorización de tamiz cuadrático". Avances en criptología, Proc. Eurocripta '84 . Apuntes de conferencias sobre informática. vol. 209. Berlín: Springer-Verlag. págs. 169–182. doi :10.1007/3-540-39757-4_17. ISBN 978-3-540-16076-2. SEÑOR  0825590.
• Pomerancia, Carl (1996). "Una historia de dos tamices" (PDF) . Avisos de la Sociedad Matemática Estadounidense . 43 (12): 1473-1485. SEÑOR  1416721.
• Silverman, Robert D. (1987). "El tamiz cuadrático polinómico múltiple". Matemáticas de la Computación . 48 (177): 329–339. doi : 10.1090/S0025-5718-1987-0866119-8 . SEÑOR  0866119.
• Trappe, W.; Washington, LC (2006). Introducción a la criptografía con teoría de la codificación (Segunda ed.). Saddle River, Nueva Jersey: Pearson Prentice Hall. ISBN 978-0-13-186239-5. SEÑOR  2372272.
• Samuel S. Wagstaff, Jr. (2013). El placer del factoraje. Providence, RI: Sociedad Estadounidense de Matemáticas. págs. 173-190. ISBN 978-1-4704-1048-3.
• Watras, Marcin (2008). Criptografía, análisis de números y números muy grandes . Bydgoszcz: Wojciechowski-Steinhagen. Pl:5324564.

enlaces externos

• Factorización utilizando el método de curva elíptica, una aplicación WebAssembly que utiliza ECM y cambia al tamiz cuadrático autoinicializador cuando es más rápido.
• GMP-ECM Archivado el 12 de septiembre de 2009 en Wayback Machine , una implementación eficiente de ECM.
• ECMNet, una sencilla implementación cliente-servidor que funciona con varios proyectos de factorización.
• pyecm, una implementación en Python de ECM.
• Proyecto de computación distribuida yoyo@Home Subproyecto ECM es un programa de factorización de curvas elípticas que se utiliza para encontrar factores para diferentes tipos de números.
• Código fuente del algoritmo de factorización de curva elíptica Lenstra Código fuente del algoritmo de factorización de curva elíptica C simple y GMP.
• EECM-MPFQ Una implementación de ECM que utiliza curvas de Edwards escritas con la biblioteca de campos finitos MPFQ.