Factorización de curva elíptica de Lenstra

Algoritmo para la 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 rápido, de tiempo de ejecución subexponencial, para la factorización de números 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 la criba cuadrática de polinomios múltiples , y el más rápido es la criba de campo numérico general . La factorización de curva elíptica de Lenstra recibe su nombre de Hendrik Lenstra .

En términos prácticos, 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 excedan 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 de por el 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 usando 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.

Algoritmo

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

1. Elija una curva elíptica aleatoria sobre (los 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 un valor aleatorio y luego configurándolo para garantizar 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 la suma de dos puntos de 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 adición implican tomar la pendiente modular de una cuerda que une y , y por lo tanto la división entre clases de residuos módulo , realizada 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; sino que, más importante aún, 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. Calcular sobre la curva elíptica ( ), donde es un producto de muchos números pequeños: digamos, un producto de 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 factor pequeño a la vez. Digamos que, para obtener , primero se calcula , luego , luego , y así sucesivamente. se elige para que sea lo suficientemente pequeño como para que la suma de puntos por punto 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 intentar nuevamente con una curva y un punto de partida diferentes. ${\displaystyle {\bmod {n}}}$
   • Si nos encontramos con un estamos acabados: 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 por exp[( √ 2  +  o (1)) √ ln  p  ln ln  p ] , donde p es el factor más pequeño de n , o , en notación L. ${\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 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 en la curva módulo p implica que k divide a N _p ; además, . 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 (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 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 este es el caso, kP no existe en la curva original, y en los cálculos encontramos algún v con gcd( v , p ) =  p o gcd( v ,  q ) =  q , pero no ambos. Es decir, gcd( v ,  n ) dio un factor no trivial de  n . ${\displaystyle \boxplus }$ ${\displaystyle kP=\infty }$ ${\displaystyle N_{p}P=\infty }$

El algoritmo 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-suave en potencias 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 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.

El ECM supera 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 (de manera 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 pruebas de que se encontrará un orden de grupo suave en el intervalo de Hasse, al usar métodos probabilísticos heurísticos , el teorema de Canfield–Erdős–Pomerance con opciones de parámetros adecuadamente optimizadas y la notación L , podemos esperar probar curvas L [ √ 2 /2, √ 2 ] antes de obtener un orden de grupo suave. Esta estimación heurística es muy confiable en la práctica.

Ejemplo de uso

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

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 ). Solo para comprobar que este 2 P está de hecho 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 al revé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 lo 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). Solo para comprobar que este es efectivamente un punto en la curva: y ² = 54514 = x ³ + 5 x – 5 (mod 455839). Después de esto, podemos calcular . ${\displaystyle 3(2P)=4P\boxplus 2P}$

De manera similar, podemos calcular 4! P , y así sucesivamente, pero 8! P requiere invertir 599 (mod 455839). El algoritmo euclidiano indica 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 ^{· 7} · 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. 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 tanto, la suma repetida se rompió aquí, produciendo la factorización.

El algoritmo con coordenadas proyectivas

Antes de considerar el plano proyectivo sobre , consideremos primero un espacio proyectivo 'normal' sobre : 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. Nótese 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 manera única, como 'puntos en el infinito' que se usan en el plano afín ( X, Y ) 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, solo se utiliza la estructura de grupo de una curva elíptica sobre el cuerpo. Dado que no necesitamos necesariamente el cuerpo , un cuerpo finito también proporcionará una estructura de grupo en una curva elíptica. Sin embargo, considerar la misma curva y operación sobre con n no primo no da un grupo. El método de la curva elíptica hace uso de los casos de falla de la ley de la adición. ${\displaystyle \mathbb {R} }$ ${\displaystyle \mathbb {R} }$ ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )/\sim }$

Ahora enunciamos el algoritmo en coordenadas proyectivas. El elemento neutro viene dado por el punto en el infinito . Sea n un entero (positivo) y consideremos la curva elíptica (un conjunto de puntos con cierta 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 forma de Weierstrass dada por y al usar 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 (denotado 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. Calcular ( k veces) en el anillo . Nótese que si es B -suave y n es primo (y por lo tanto es un cuerpo) que . Sin embargo, si solo es B-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. Si no es así, vuelva 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 (Factorización de números enteros con curvas elípticas), la suma necesita el supuesto . Si no son y son 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)}$

• 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 será por un error de cálculo. En particular, porque no siempre se puede calcular si n no es primo (y por lo tanto no es un cuerpo). Sin hacer uso de que sea un cuerpo, 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 es siempre legal 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 .

Curvas de Edwards retorcidas

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

Definición. Sea un cuerpo 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 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 la adición 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 forma similar a cómo la curva de Weierstrass proyectiva se desprende 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 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 la 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\}.}$

Toda curva de Edwards con un punto de orden 3 se puede escribir de las formas que se muestran arriba. Las curvas con un grupo de torsión isomorfo a y pueden ser más eficientes para encontrar 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. En ella, 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 un 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. La comprobación de un orden pequeño de , se puede realizar calculando el módulo n para cada primo l . ${\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 curvas elípticas 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)

Existen desarrollos 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 (es decir, una curva con f de grado 5), que da el mismo resultado que usar dos curvas elípticas "normales" al mismo tiempo. Al hacer uso de la superficie de Kummer, el cálculo es más eficiente. Las desventajas de la curva hiperelíptica (en comparación con una curva elíptica) se compensan con esta forma alternativa de cálculo. Por lo tanto, Cosset afirma en términos generales que el uso de curvas hiperelípticas para la factorización no es peor que el uso de 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 duplicar aproximadamente la longitud de los primos encontrados en comparación con 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 .(ver 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 postcuántico. En: Lange T., Takagi T. (eds), Criptografía postcuántica . PQCrypto 2017. Notas de clase en 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 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.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 Bibliográfico :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 del campo numérico. Lecture Notes in Mathematics. Vol. 1554. Berlín: Springer-Verlag. doi :10.1007/BFb0091534. ISBN 978-3-540-57013-4. Sr.  1321216.
• Lenstra Jr., HW (1987). "Factorización de 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. MR  0916721.
• Pomerance, Carl ; Crandall, Richard (2005). Números primos: una perspectiva computacional (segunda edición). Nueva York: Springer. ISBN 978-0-387-25282-7.Sr. 2156291  .
• Pomerance, Carl (1985). "El algoritmo de factorización de criba cuadrática". Avances en criptología, Proc. Eurocrypt '84 . Apuntes de clase en 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.Sr. 0825590  .
• Pomerance, Carl (1996). "Un cuento de dos tamices" (PDF) . Avisos de la American Mathematical Society . 43 (12): 1473–1485. MR  1416721.
• Silverman, Robert D. (1987). "La criba cuadrática de polinomios múltiples". Matemáticas de la computación . 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 codificación (segunda edición). Saddle River, NJ: Pearson Prentice Hall. ISBN 978-0-13-186239-5.Señor 2372272  .
• Samuel S. Wagstaff, Jr. (2013). El placer de factorizar. Providence, RI: American Mathematical Society. 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 autoinicializante 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 de Python de ECM.
• 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 utilizando curvas de Edwards escritas con la biblioteca de campos finitos MPFQ.