The Elliptic Curve Method for Integer Factorization (ECM)
Sage includes GMP-ECM, which is a highly optimized implementation of Lenstra’s elliptic curve factorization method. See http://ecm.gforge.inria.fr/ for more about GMP-ECM. This file provides a Cython interface to the GMP-ECM library.
sage: from sage.libs.libecm import ecmfactor sage: result = ecmfactor(999, 0.00) sage: result in [(True, 27), (True, 37), (True, 999)] True sage: result = ecmfactor(999, 0.00, verbose=True) Performing one curve with B1=0 Found factor in step 1: ... sage: result in [(True, 27), (True, 37), (True, 999)] True
Try to find a factor of a positive integer using ECM (Elliptic Curve Method). This function tries one elliptic curve.
Either (False, None) if no factor was found, or (True, f) if the factor f was found.
sage: from sage.libs.libecm import ecmfactor
This number has a small factor which is easy to find for ECM:
sage: N = 2^167 - 1 sage: factor(N) 2349023 * 79638304766856507377778616296087448490695649 sage: ecmfactor(N, 2e5) (True, 2349023)
With a smaller B1 bound, we may or may not succeed:
sage: ecmfactor(N, 1e2) # random (False, None)
The following number is a Mersenne prime, so we don’t expect to find any factors (there is an extremely small chance that we get the input number back as factorization):
sage: N = 2^127 - 1 sage: N.is_prime() True sage: ecmfactor(N, 1e3) (False, None)
If we have several small prime factors, it is possible to find a product of primes as factor:
sage: N = 2^179 - 1 sage: factor(N) 359 * 1433 * 1489459109360039866456940197095433721664951999121 sage: ecmfactor(N, 1e3) # random (True, 514447)
We can ask for verbose output:
sage: N = 12^97 - 1 sage: factor(N) 11 * 43570062353753446053455610056679740005056966111842089407838902783209959981593077811330507328327968191581 sage: ecmfactor(N, 100, verbose=True) Performing one curve with B1=100 Found factor in step 1: 11 (True, 11) sage: ecmfactor(N/11, 100, verbose=True) Performing one curve with B1=100 Found no factor. (False, None)
Check that ecmfactor can be interrupted (factoring a large prime number):
sage: import sage.tests.interrupt sage: try: ... sage.tests.interrupt.interrupt_after_delay() ... ecmfactor(2^521-1, 1e7) ... except KeyboardInterrupt: ... print "Caught KeyboardInterrupt" Caught KeyboardInterrupt
Some special cases:
sage: ecmfactor(1, 100) (True, 1) sage: ecmfactor(0, 100) Traceback (most recent call last): ... ValueError: Input number (0) must be positive