Factorización de curvas elípticas de Lenstra

La factorización de curvas elípticas de Lenstra o método de factorización de curvas elípticas ( ECM ) es un algoritmo rápido, de tiempo de ejecución subexponencial, 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 método de cribado cuadrático de polinomios múltiples , y el más rápido es el método de cribado de cuerpos numéricos generales . La factorización de curvas elípticas de Lenstra recibe su nombre de Hendrik Lenstra . Es un algoritmo de factorización de grupos algebraicos .

En la práctica, ECM se considera un algoritmo de factorización de propósito especial, ya que es el más adecuado para encontrar factores pequeños. ActualmenteSigue siendo el mejor algoritmo para divisores que no superan los 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 entero muy grande con muchos factores; si el entero restante sigue siendo compuesto, entonces solo tiene factores grandes y se factoriza utilizando técnicas de propósito general. El factor más grande encontrado utilizando ECM hasta ahora 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 en el número de dígitos.

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${\displaystyle \boxplus }$-adición son ahora grupos genuinos . Si estos grupos tienen N _p y N _q elementos, respectivamente, entonces para cualquier punto P en la curva original, por el teorema de Lagrange , k  >  0 es mínimo tal que${\displaystyle kP=\infty }$en la curva módulo p implica que k divide a N _p ; además,${\displaystyle N_{p}P=\infty }$La afirmación análoga se cumple para la curva módulo q . Cuando la curva elíptica se elige aleatoriamente, entonces N _p y N _q son números aleatorios cercanos a p  +  1 y q  +  1, respectivamente (véase más abajo). Por lo tanto, es improbable que la mayoría de los factores primos de N _p y N _q sean los mismos, y es bastante probable que al calcular eP , encontremos algún kP que sea ∞ módulo p  pero no módulo q ,  o viceversa. Cuando esto ocurre, kP no existe en la curva original, y en los cálculos encontramos algún v con mcd( v , p )  = p  o mcd( v , q ) = q ,    pero no ambos. Es decir, mcd( v , n )  dio un factor no trivial de n . 

ECM es esencialmente una mejora del antiguo algoritmo p − 1.   El algoritmo p − 1   encuentra factores primos p tales que p − 1   es b-potencia suave para valores pequeños de b . Para cualquier e , un múltiplo de p − 1,   y cualquier a relativamente primo a p , por el pequeño teorema de Fermat tenemos a ^e ≡ 1 ( mod p )   . Entonces mcd ( a ^e − 1, n )    probablemente producirá 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 al considerar 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 (de forma bastante aleatoria) 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 prueba de que se encontrará un orden de grupo suave 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.

El siguiente ejemplo proviene de Trappe y Washington (2006) , con algunos detalles añadidos.

Queremos tener en cuenta${\displaystyle n=455839}$. Elegimos la curva elíptica${\displaystyle y^{2}=x^{3}+5x-5}$, con el punto${\displaystyle P=(1,1)}$sobre él, y tratemos de calcular el punto${\displaystyle (10!)P}$.

La pendiente de la línea tangente en algún punto${\displaystyle A=(x,y)}$en la curva es${\displaystyle \lambda ={\frac {3x^{2}+5}{2y}}\ (\mathrm {mod} \ n)}$. Usando${\displaystyle \lambda }$, podemos calcular el punto${\displaystyle 2A}$. Si el valor de${\displaystyle \lambda }$no existe, como resultado de${\displaystyle y}$no tener un inverso modular , entonces${\displaystyle \gcd(n,y)}$es un factor no trivial de${\displaystyle n}$.

Primero, calculamos${\displaystyle 2!P}$. Usando duplicación de puntos , tenemos${\displaystyle \lambda (P)=\lambda (1,1)=4}$, por lo tanto, las coordenadas del punto${\displaystyle 2P=(x',y')}$son

${\displaystyle x'=4^{2}-2(1)=14}$

${\displaystyle y'=4(1-14)-1=-53}$

cediendo el punto${\displaystyle 2P=(14,-53)}$.

A continuación, calculamos${\displaystyle 3!P}$. Tenemos${\displaystyle \lambda (2P)=\lambda (14,-53)=-593/106\ (\mathrm {mod} \ n)}$. Desde${\displaystyle \gcd(106,455839)=1}$, el inverso modular de 106 existe. Usando el algoritmo euclidiano extendido , podemos obtener que${\displaystyle \lambda =-593/106=322522\ (\mathrm {mod} \ 455839)}$.

Dado esto, podemos calcular las coordenadas de${\displaystyle 2(2P)}$, tal como lo hicimos anteriormente. Las coordenadas del punto${\displaystyle 4P=(x',y')}$son

${\displaystyle x'=322522^{2}-2(14)=259851{\pmod {455839}}}$

${\displaystyle y'=322522(14-259851)-(-53)=116255{\pmod {455839}}}$

Esto produce${\displaystyle 4P=(259851,116255)}$.

Después de esto, podemos calcular${\displaystyle 3(2P)=4P+2P}$usando la suma de puntos . La línea que une${\displaystyle 4P}$y${\displaystyle 2P}$tiene pendiente${\displaystyle \lambda =116308/259837=206097\ (\mathrm {mod} \ n)}$, por lo tanto las coordenadas de${\displaystyle 6P=(x',y')}$son

${\displaystyle x'=206097^{2}-14-259851=179685{\pmod {455839}}}$

${\displaystyle y'=206097(14-179685)-(-53)=427131{\pmod {455839}}}$

cediendo el punto${\displaystyle 6P=(179685,427131)}$

Podemos calcular puntos de manera similar${\displaystyle 4!P}$,${\displaystyle 5!P}$y así sucesivamente, pero la computación${\displaystyle 8!P}$requiere invertir 599 (mod 455839) , lo cual no es posible porque${\displaystyle \gcd(599,455839)=599\neq 1}$. Por lo tanto, 599 es un divisor de 455839. Después de una división rápida, tenemos 455839 = 599 × 761 .

La razón por la que esto funciona 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 las curvas (mod 599) y (mod 761), respectivamente. Como 8! es un múltiplo de 640 pero no de 777, tenemos 8! P = ∞ en la curva (mod 599), pero no en la curva (mod 761), por lo que la suma repetida falló aquí, dando como resultado la factorización.

Antes de considerar el plano proyectivo sobre${\displaystyle (\mathbb {Z} /n\mathbb {Z} )/\sim ,}$Consideremos primero un espacio proyectivo 'normal' sobre${\displaystyle \mathbb {R} }$En lugar de puntos, se estudian líneas que pasan por el origen. Una línea puede representarse como un punto distinto de cero.${\displaystyle (x,y,z)}$, bajo una relación de equivalencia ~ dada por:${\displaystyle (x,y,z)\sim (x',y',z')}$⇔ Existe c ≠ 0 tal que x' = c x , y' = c y y z' = c z . Bajo esta relación de equivalencia, el espacio se denomina plano proyectivo.${\displaystyle \mathbb {P} ^{2}}$; puntos, denotados por${\displaystyle (x:y:z)}$, corresponden a líneas en un espacio tridimensional que pasan por el origen. Nótese que el punto${\displaystyle (0:0:0)}$no existe en este espacio ya que para trazar 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 ) sobre el que se encuentra.

La coordenada ${\displaystyle (x:y:z)}$corresponde a ${\displaystyle (x/z:y/z)}$en el espacio afín. ^{[ 2 ]}

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

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

1. Elegir${\displaystyle x_{P},y_{P},a\in \mathbb {Z} /n\mathbb {Z} }$con a ≠ 0.
2. Calcular${\displaystyle b=y_{P}^{2}-x_{P}^{3}-ax_{P}}$La curva elíptica E está entonces en forma de Weierstrass dada por${\displaystyle y^{2}=x^{3}+ax+b}$y utilizando coordenadas proyectivas la curva elíptica viene dada por la ecuación homogénea${\displaystyle ZY^{2}=X^{3}+aZ^{2}X+bZ^{3}}$Tiene sentido.${\displaystyle P=(x_{P}:y_{P}:1)}$.
3. Elija un límite superior${\displaystyle B\in \mathbb {Z} }$para esta curva elíptica.
   • Nota: Solo encontrará factores p si el orden de grupo g de la curva elíptica E sobre${\displaystyle \mathbb {Z} /p\mathbb {Z} }$(denotado por${\displaystyle \#E(\mathbb {Z} /p\mathbb {Z} )}$) es B-suave , lo que significa que todos los factores primos de${\displaystyle n}$tienen que ser menores o iguales a B.
4. Calcular${\displaystyle k={\rm {lcm}}(1,\dots ,B)}$.
5. Calcular${\displaystyle kP:=P+P+\cdots +P}$(la multiplicación es una suma repetida) en el anillo${\displaystyle E(\mathbb {Z} /n\mathbb {Z} )}$.
   • Si el cálculo se realiza correctamente, devuelve${\displaystyle kP=(0:1:0)}$Esto significa que g no es B -suave o que n es primo. Vuelve al paso 2 para elegir otra curva.
   • Si el cálculo falla en algún punto, significa que se puede encontrar un divisor no trivial. Puede fallar porque la suma y la multiplicación no están bien definidas si n no es primo, pero esto solo ocurre cuando se intenta una inversión de un residuo v en particular . En este caso, el factor se encuentra como${\displaystyle \gcd(v,n)}$como se indicó anteriormente.

En el punto 5 se dice que, bajo 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 requiere la suposición${\displaystyle \gcd(x_{1}-x_{2},n)=1}$. Si${\displaystyle P,Q}$no lo son${\displaystyle (0:1:0)}$y distintos (de lo contrario, la suma funciona de manera similar, pero es un poco diferente), entonces la suma funciona de la siguiente manera:

• Para 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 error de cálculo.${\displaystyle \lambda .}$En particular, porque${\displaystyle (x_{1}-x_{2})^{-1}}$no siempre se puede calcular si n no es primo (y por lo tanto${\displaystyle \mathbb {Z} /n\mathbb {Z} }$no es un campo). Sin hacer uso de${\displaystyle \mathbb {Z} /n\mathbb {Z} }$Siendo un campo, se podría calcular:

• ${\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 válido y si el mcd de la coordenada Z con n ≠ (1 o n ), entonces cuando la simplificación falla, se encuentra un divisor no trivial de n .

El uso de curvas de Edwards requiere menos multiplicaciones modulares y menos tiempo que el uso de curvas de Montgomery o Weierstrass (otros métodos utilizados). Además, con las curvas de Edwards se pueden encontrar más números primos.

Definición. Deje${\displaystyle k}$ser un campo en el que${\displaystyle 2\neq 0}$y dejar${\displaystyle a,d\in k\setminus \{0\}}$con${\displaystyle a\neq d}$Luego, la curva retorcida de Edwards.${\displaystyle E_{E,a,d}}$es dado por${\displaystyle ax^{2}+y^{2}=1+dx^{2}y^{2}.}$Una curva de Edwards es una curva de Edwards retorcida en la que${\displaystyle a=1}$.

Existen 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 completados.

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 adición viene 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${\displaystyle (e,f)}$es${\displaystyle (-e,f)}$.

Las demás representaciones se definen de forma similar a como la curva proyectiva de Weierstrass se deriva de la afín.

Cualquier curva elíptica en forma de Edwards tiene un punto de orden 4. Por lo tanto, el grupo de torsión de una curva de Edwards sobre${\displaystyle \mathbb {Q} }$es isomorfo a cualquiera${\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} }$o${\displaystyle \mathbb {Z} /2\mathbb {Z} \times \mathbb {Z} /8\mathbb {Z} }$.

Los casos más interesantes para ECM son:${\displaystyle \mathbb {Z} /12\mathbb {Z} }$y${\displaystyle \mathbb {Z} /2\mathbb {Z} \times \mathbb {Z} /8\mathbb {Z} }$, 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 x^{2}+y^{2}=1+dx^{2}y^{2}}$con punto${\displaystyle (a,b)}$dónde${\displaystyle b\notin \{-2,-1/2,0,\pm 1\},a^{2}=-(b^{2}+2b)}$y${\displaystyle d=-(2b+1)/(a^{2}b^{2})}$
• ${\displaystyle x^{2}+y^{2}=1+dx^{2}y^{2}}$con punto${\displaystyle (a,b)}$dónde${\displaystyle a={\frac {u^{2}-1}{u^{2}+1}},b=-{\frac {(u-1)^{2}}{u^{2}+1}}}$y${\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 las formas que se muestran arriba. Curvas con grupo de torsión isomorfo a${\displaystyle \mathbb {Z} /2\mathbb {Z} \times \mathbb {Z} /8\mathbb {Z} }$y${\displaystyle \mathbb {Z} /2\mathbb {Z} \times \mathbb {Z} /4\mathbb {Z} }$puede ser más eficiente para encontrar números primos. ^{[ 6 ]}

GMP-ECM de Paul Zimmerman es una implementación de propósito general del algoritmo Lenstra basada en la biblioteca aritmética de precisión múltiple de GNU . Se ha actualizado continuamente, siendo la última versión a septiembre de 2025 la 7.0.6 de julio de 2024. Permite curvas Montgomery, Weierstrass y Hessiana (retorcida). Puede ejecutar la etapa 1 para un subconjunto de curvas Montgomery en una GPU CUDA , y la implementación anterior de Cyril Bouvier en 2012 fue reemplazada por la implementación más reciente de Seth Troisi en 2021. La versión 7.0.6 también incluye una implementación del método HECM (descrito a continuación), los métodos p-1 y p+1, y prueba de primalidad usando APRCL. ^{[ 7 ]} GMP-ECM se usa en SageMath .

Daniel J. Bernstein y sus colaboradores publicaron una serie de implementaciones basadas en curvas elípticas de Twisted Edwards entre 2008 y 2010. Todas afirman superar el rendimiento de la versión contemporánea de GMP-ECM, siendo la más reciente EECM-MPFQ de 2008. Bernstein también ofrece dos implementaciones para GPU, siendo CUDA-EECM de 2009 la más reciente y rápida. ^{[ 6 ] [ 8 ]}

Prime95 incluye una implementación de Lenstra ECM para curvas de Montgomery y Edwards. Se utiliza para el subproyecto ECM de Great Internet Mersenne Prime Search , que busca factorizar números de Mersenne compuestos no menores que ^2¹²¹³ . ^{[ 9 ]} Puede producir una salida de etapa 1 compatible con GMP-ECM, así como consumir la salida de etapa 1 de GMP-ECM. ^{[ 10 ]} Es más rápido que GMP-ECM en la etapa 1. ^{[ 11 ]}

John Wloka y sus colaboradores publicaron en 2020 ecmongpu, una implementación de las etapas 1 y 2 de Lenstra ECM basada en curvas elípticas de Twisted Edwards. Su artículo informa sobre el rendimiento para factorizar módulos de hasta 448 bits de longitud (entre 2⁴⁴⁷ ^y 2⁴⁴⁸ ^- 1). ^{[ 12 ]}

Todo el software mencionado anteriormente es de código abierto. Además, el software de código abierto PARI/GP y el sistema propietario Magma (sistema de álgebra computacional) también contienen "buenas implementaciones de ECM", según Paul Zimmerman. ^{[ 11 ]} Una implementación de software anterior de 16 bits ^{[ 13 ]} es giantint, de Richard Crandall. ^{[ 11 ]}

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 con género dos (por lo que una curva${\displaystyle y^{2}=f(x)}$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 alternativa de cálculo. Por lo tanto, Cosset afirma, en términos generales, que usar curvas hiperelípticas para la factorización no es peor que usar curvas elípticas.

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

• 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 en Filosofía. 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. Bibcode : 1999MaCom..68..429B . doi : 10.1090/S0025-5718-99-00992-8 . MR 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. MR 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 . Bibcode : 2010MaCom..79.1191C . doi : 10.1090/S0025-5718-09-02295-9 . MR 2600562. S2CID 914296 .  
• Lenstra, AK ; Lenstra Jr., HW, eds. (1993). El desarrollo de la criba de cuerpos numéricos . Lecture Notes in Mathematics. Vol.  1554. Berlín: Springer-Verlag. pp. 11–42 . doi : 10.1007/BFb0091534 . ISBN  978-3-540-57013-4MR 1321216 .​ 
• Lenstra Jr., HW (1987). "Factoring integers with elliptic curves" (PDF) . Annals of Mathematics . 126 (3): 649– 673. doi : 10.2307/1971363 . hdl : 1887/2140 . JSTOR 1971363. MR 0916721 .  
• Pomerance, Carl ; Crandall, Richard (2005). Números primos: una perspectiva computacional (segunda  edición). Nueva York: Springer. ISBN 978-0-387-25282-7MR 2156291 .​ 
• Pomerance, Carl (1985). «El algoritmo de factorización de criba cuadrática». Avances en criptología, Actas de Eurocrypt '84 . Notas de clase en informática. Vol.  209. Berlín: Springer-Verlag. pp. 169–182 . doi : 10.1007/3-540-39757-4_17 . ISBN  978-3-540-16076-2. SR 0825590 . 
• Pomerance, Carl (1996). "Un cuento de dos tamices" (PDF) . Notices of the American Mathematical Society . 43 (12): 1473– 1485. MR 1416721 . 
• Silverman, Robert D. (1987). "The Multiple Polynomial Quadratic Sieve" . Mathematics of Computation . 48 (177): 329– 339. doi : 10.1090/S0025-5718-1987-0866119-8 . MR 0866119 . 
• Trappe, W.; Washington, LC (2006). Introducción a la criptografía con teoría de la codificación (Segunda  edición). Saddle River, NJ: Pearson Prentice Hall. ISBN 978-0-13-186239-5. MR 2372272 . 
• Samuel S. Wagstaff, Jr. (2013). El placer de factorizar . Providence, RI: American Mathematical Society. pp. 173–190 . ISBN  978-1-4704-1048-3.
• Watras, Marcin (2008). Criptografía, análisis numérico y números muy grandes . Bydgoszcz: Wojciechowski-Steinhagen. PL:5324564.

• Factorización mediante el método de curva elíptica , una aplicación WebAssembly que utiliza ECM y cambia al método de criba cuadrática autoinicializable cuando es más rápido.
• GMP-ECM se archivó el 12 de septiembre de 2009 en Wayback Machine ; es una implementación eficiente de ECM.
• ECMNet , una implementación cliente-servidor sencilla que funciona con varios proyectos de factorización.
• pyecm , una implementación en Python de ECM.
• El proyecto de computación distribuida yoyo@Home, subproyecto ECM, es un programa para la 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 curvas elípticas de Lenstra. Código fuente del algoritmo de factorización de curvas elípticas simple en C y GMP.
• EECM-MPFQ: Una implementación de ECM que utiliza curvas de Edwards, escrita con la biblioteca de campos finitos MPFQ.