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 Computation68 (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. ISBN0-387-55640-0.
Cosset, R. (2010). «Factorization with genus 2 curves». Mathematics of Computation79 (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 Mathematics126 (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. ISBN0-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.
Silverman, Robert D. (1987). «The Multiple Polynomial Quadratic Sieve». Mathematics of Computation48 (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. ISBN0-13-186239-1.
Watras, Marcin (2008). Cryptography, Number Analysis, and Very Large Numbers. Bydgoszcz: Wojciechowski-Steinhagen. PL:5324564.
Enlaces externos
Factorization using the Elliptic Curve Method, a Java applet which uses ECM and switches to the Self-Initializing Quadratic Sieve when it is faster.
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.
Datos:Q2662711
Diciembre 29, 2021
factorización, curva, elíptica, lenstra, factorización, curva, elíptica, lenstra, método, factorización, curva, elíptica, inglés, elliptic, curve, factorization, method, rápido, algoritmo, tiempo, ejecución, exponencial, para, factorización, enteros, emplea, c. La factorizacion de curva eliptica de Lenstra o metodo de factorizacion de curva eliptica del ingles elliptic curve factorization method ECM es un rapido algoritmo de tiempo de ejecucion sub exponencial para la factorizacion de enteros que emplea curvas elipticas Para una factorizacion de proposito general ECM es el tercer metodo mas rapido conocido de factorizacion El segundo mas rapido es la criba cuadratica de multiples polinomios y el mas rapido es la criba general del cuerpo de numeros La factorizacion de curva eliptica de Lenstra es llamada asi en honor a Hendrik Lenstra En la practica ECM es considerado un algoritmo de factorizacion de proposito especial asi como el mas adecuado para encontrar factores pequenos A fecha de 2012 es todavia el mejor algoritmo para divisores que no superen los 20 a 25 digitos decimales 64 a 83 bits respectivamente asi como su tiempo de ejecucion esta dominado por el tamano del factor mas pequeno p en lugar de por el tamano del numeron a ser factorizado Frecuentemente ECM se usa para eliminar factores pequenos de un entero muy grande con muchos factores si el entero resultante todavia es compuesto entonces solo tiene factores grandes y es factorizado mediante el uso de tecnicas de proposito general El factor mas grande encontrado usando ECM cuenta con 75 digitos y fue descubierto el 2 de agosto de 2012 por Samuel Wagstaff 1 Incrementando el numero de curvas probadas se mejoran las posibilidades de encontrar un factor pero no son lineales con el incremento en el numero de digitos Referencias Editar 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 edicion 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 edicion 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 EditarFactorization using the Elliptic Curve Method a Java applet which uses ECM and switches to the Self Initializing Quadratic Sieve when it is faster 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 Datos Q2662711 Obtenido de https es wikipedia org w index php title Factorizacion de curva eliptica de Lenstra amp oldid 137777431, wikipedia, wiki, leyendo, leer, libro, biblioteca,
