Factorización de curva elíptica de Lenstra

La factorización de curva elíptica de Lenstra o método de factorización de curva elíptica ( del inglés elliptic curve factorization method, ECM) es un rápido algoritmo de tiempo de ejecución sub-exponencial para la factorización de enteros que emplea curvas elípticas. Para una factorización de propósito general, ECM es el tercer método más rápido conocido de factorización. El segundo más rápido es la criba cuadrática de múltiples polinomios y el más rápido es la criba general del cuerpo de números. La factorización de curva elíptica de Lenstra es llamada así en honor a Hendrik Lenstra.

En la práctica, ECM es considerado un algoritmo de factorización de propósito especial así como el más adecuado para encontrar factores pequeños. A fecha de 2012, es todavía el mejor algoritmo para divisores que no superen los 20 a 25 dígitos decimales (64 a 83 bits respectivamente), así como 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 ser factorizado. Frecuentemente, ECM se usa para eliminar factores pequeños de un entero muy grande con muchos factores; si el entero resultante todavía es compuesto, entonces solo tiene factores grandes y es factorizado mediante el uso de técnicas de propósito general. El factor más grande encontrado usando ECM cuenta con 75 dígitos y fue descubierto el 2 de agosto de 2012 por Samuel Wagstaff.^[1] Incrementando el número de curvas probadas se mejoran las posibilidades de encontrar un factor, pero no son lineales con el incremento en el número de dígitos.

Referencias

↑ 50 largest factors found by ECM

Bernstein, D. J.; Birkner, P.; Lange, T.; Peters, C. (2008). «ECM using Edwards curves». ePrint archive 2008/016.
Bosma, W.; Hulst, M. P. M. van der (1990). Primality proving with cyclotomy. Ph.D. Thesis, Universiteit van Amsterdam. OCLC 256778332.
Brent, Richard P. (1999). «Factorization of the tenth Fermat number». Mathematics of Computation 68 (225): 429-451. doi:10.1090/S0025-5718-99-00992-8.
Cohen, Henri (1996). A Course in Computational Algebraic Number Theory. New York, Berlin, Heidelberg: Springer-Verlag. ISBN 0-387-55640-0.
Cosset, R. (2010). «Factorization with genus 2 curves». Mathematics of Computation 79 (270): 1191-1208. doi:10.1090/S0025-5718-09-02295-9.
Lenstra, A. K.; Lenstra Jr., H. W., eds. (1993). The development of the number field sieve. Lecture Notes in Mathematics 1554. Berlin: Springer-Verlag. MR 96m:11116.
Lenstra Jr., H. W. (1987). «Factoring integers with elliptic curves». Annals of Mathematics 126 (3): 649-673. JSTOR 1971363. MR 89g:11125.
Pomerance, Carl; Richard Crandall (2001). «Section 7.4: Elliptic curve method». Prime Numbers: A Computational Perspective (1st edición). Springer. pp. 301–313. ISBN 0-387-94777-9.
Pomerance, Carl (1985). «The quadratic sieve factoring algorithm». Advances in Cryptology, Proc. Eurocrypt '84. Lecture Notes in Computer Science 209. Berlin: Springer-Verlag. pp. 169-182. MR 87d:11098.
Pomerance, Carl (1996). «A Tale of Two Sieves» (PDF). Notices of the American Mathematical Society 43 (12): 1473-1485.
Silverman, Robert D. (1987). «The Multiple Polynomial Quadratic Sieve». Mathematics of Computation 48 (177): 329-339. doi:10.1090/S0025-5718-1987-0866119-8.
Trappe, W.; Washington, L. C. (2006). Introduction to Cryptography with Coding Theory (Second edición). Pearson Prentice Hall. ISBN 0-13-186239-1.
Watras, Marcin (2008). Cryptography, Number Analysis, and Very Large Numbers. Bydgoszcz: Wojciechowski-Steinhagen. PL:5324564.

Enlaces externos

Calculadora de factorización de números enteros es una aplicación web para la factorización de enteros que usa el método de la curva elíptica y la criba cuadrática auto-inicializada.
GMP-ECM, an efficient implementation of ECM.
ECMNet, an easy client-server implementation that works with several factorization projects.
pyecm, a python implementation of ECM. Much faster with psyco and/or gmpy.
Distributed computing project yoyo@Home Subproject ECM is a program for Elliptic Curve Factorization which is used by a couple of projects to find factors for different kind of numbers.