The elliptic curve factorization method (ECM) is the fastest way to factor a known composite integer if one of the factors is relatively small (up to approximately 80 bits / 25 decimal digits). To factor an arbitrary integer it must be combined with a primality test. The ECM.factor() method is an example for how to combine ECM with a primality test to compute the prime factorization of integers.
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.
AUTHORS:
These people wrote GMP-ECM: Pierrick Gaudry, Jim Fougeron, Laurent Fousse, Alexander Kruppa, Dave Newman, Paul Zimmermann
BUGS:
Output from ecm is non-deterministic. Doctests should set the random seed, but currently there is no facility to do so.
Bases: sage.structure.sage_object.SageObject
Create an interface to the GMP-ECM elliptic curve method factorization program.
See http://ecm.gforge.inria.fr
INPUT:
In addition the following keyword arguments can be used:
Return a probable prime factorization of \(n\).
Combines GMP-ECM with a primality test, see is_prime(). The primality test is provable or probabilistic depending on the \(proof\) flag.
Moreover, for small \(n\) PARI is used directly.
Warning
There is no mathematical guarantee that the factors returned are actually prime if proof=False (default). It is extremely likely, though. Currently, there are no known examples where this fails.
INPUT:
OUTPUT:
A list of integers whose product is n.
Note
Trial division should typically be performed, but this is not implemented (yet) in this method.
If you suspect that n is the product of two similarly-sized primes, other methods (such as a quadratic sieve – use the qsieve command) will usually be faster.
The best known algorithm for factoring in the case where all factors are large is the general number field sieve. This is not implemented in Sage; You probably want to use a cluster for problems of this size.
EXAMPLES:
sage: ecm.factor(602400691612422154516282778947806249229526581)
[45949729863572179, 13109994191499930367061460439]
sage: ecm.factor((2^197 + 1)/3) # long time
[197002597249, 1348959352853811313, 251951573867253012259144010843]
sage: ecm.factor(179427217^13) == [179427217] * 13
True
Return a factor of n.
See also factor() if you want a prime factorization of \(n\).
INPUT:
OUTPUT:
List of integers whose product is n. For certain lengths of the factor, this is the best algorithm to find a factor.
EXAMPLES:
sage: f = ECM()
sage: n = 508021860739623467191080372196682785441177798407961
sage: f.find_factor(n)
[79792266297612017, 6366805760909027985741435139224233]
Note that the input number can’t have more than 4095 digits:
sage: f=2^2^14+1
sage: ecm.find_factor(f)
Traceback (most recent call last):
...
ValueError: n must have at most 4095 digits
Return the parameters (including the curve) of the last ecm run.
In the case that the number was factored successfully, this will return the parameters that yielded the factorization.
OUTPUT:
A dictionary containing the parameters for the most recent factorization.
EXAMPLES:
sage: ecm.factor((2^197 + 1)/3) # long time
[197002597249, 1348959352853811313, 251951573867253012259144010843]
sage: ecm.get_last_params() # random output
{'poly': 'x^1', 'sigma': '1785694449', 'B1': '8885', 'B2': '1002846'}
Interactively interact with the ECM program.
EXAMPLES:
sage: ecm.interact() # not tested
Run one single ECM (or P-1/P+1) curve on input n.
Note that trying a single curve is not particularly useful by itself. One typically needs to run over thousands of trial curves to factor \(n\).
INPUT:
OUTPUT:
a list [p, q] where p and q are integers and n = p * q. If no factor was found, then p = 1 and q = n.
Warning
Neither p nor q in the output is guaranteed to be prime.
EXAMPLES:
sage: f = ECM()
sage: n = 508021860739623467191080372196682785441177798407961
sage: f.one_curve(n, B1=10000, sigma=11)
[1, 508021860739623467191080372196682785441177798407961]
sage: f.one_curve(n, B1=10000, sigma=1022170541)
[79792266297612017, 6366805760909027985741435139224233]
sage: n = 432132887883903108009802143314445113500016816977037257
sage: f.one_curve(n, B1=500000, algorithm="P-1")
[67872792749091946529, 6366805760909027985741435139224233]
sage: n = 2088352670731726262548647919416588631875815083
sage: f.one_curve(n, B1=2000, algorithm="P+1", x0=5)
[328006342451, 6366805760909027985741435139224233]
Return recommended B1 setting.
INPUT:
OUTPUT:
Integer. Recommended settings from http://www.mersennewiki.org/index.php/Elliptic_Curve_Method
EXAMPLES:
sage: ecm.recommended_B1(33)
1000000
Print a runtime estimate.
BUGS:
This method should really return something and not just print stuff on the screen.
INPUT:
OUTPUT:
An approximation for the amount of time it will take to find a factor of size factor_digits in a single process on the current computer. This estimate is provided by GMP-ECM’s verbose option on a single run of a curve.
EXAMPLES:
sage: n = next_prime(11^23)*next_prime(11^37)
sage: ecm.time(n, 35) # random output
Expected curves: 910, Expected time: 23.95m
sage: ecm.time(n, 30, verbose=True) # random output
GMP-ECM 6.4.4 [configured with MPIR 2.6.0, --enable-asm-redc] [ECM]
Running on localhost.localdomain
Input number is 304481639541418099574459496544854621998616257489887231115912293 (63 digits)
Using MODMULN [mulredc:0, sqrredc:0]
Using B1=250000, B2=128992510, polynomial Dickson(3), sigma=3244548117
dF=2048, k=3, d=19110, d2=11, i0=3
Expected number of curves to find a factor of n digits:
35 40 45 50 55 60 65 70 75 80
4911 70940 1226976 2.5e+07 5.8e+08 1.6e+10 2.7e+13 4e+18 5.4e+23 Inf
Step 1 took 230ms
Using 10 small primes for NTT
Estimated memory usage: 4040K
Initializing tables of differences for F took 0ms
Computing roots of F took 9ms
Building F from its roots took 16ms
Computing 1/F took 9ms
Initializing table of differences for G took 0ms
Computing roots of G took 8ms
Building G from its roots took 16ms
Computing roots of G took 7ms
Building G from its roots took 16ms
Computing G * H took 6ms
Reducing G * H mod F took 5ms
Computing roots of G took 7ms
Building G from its roots took 17ms
Computing G * H took 5ms
Reducing G * H mod F took 5ms
Computing polyeval(F,G) took 34ms
Computing product of all F(g_i) took 0ms
Step 2 took 164ms
Expected time to find a factor of n digits:
35 40 45 50 55 60 65 70 75 80
32.25m 7.76h 5.60d 114.21d 7.27y 196.42y 337811y 5e+10y 7e+15y Inf
Expected curves: 4911, Expected time: 32.25m