This package implements Lenstra's Elliptic Curve method of factorization. The package is designed to find prime factors of up to about 18 digits in reasonable time (up to three hours on a workstation). This extends Mathematica's integer factoring to all numbers of 40 digits or less. The program in the package is a fairly direct implementation of the algorithm described in P.L. Montgomery's, "Speeding up the Pollard and Elliptic Curve Methods of Factorization," Mathematics of Computation 48 (1987), pages 243-264.
The algorithm returns a single factor (not necessarily a prime). To obtain a complete factorization, you should use FactorIntegerECM or the built-in FactorInteger on the factor and cofactor. The algorithm is probabilistic, so there could be a large variance in running times, even for similar inputs. SeedRandom is used to generate pseudorandom numbers for the algorithm, so the program will always run exactly the same on the same input.
This loads the package.
FactorIntegerECM should be used as an enhancement to the built-in functions PrimeQ and FactorInteger. The algorithm will always fail if the input is a prime. A prime number should never be given as input to FactorIntegerECM. Before using FactorIntegerECM, you should always use PrimeQ to make sure that your number is not prime.
The algorithm is designed with the assumption that the number given was not factored by FactorInteger, and so its smallest prime factor is at least . The algorithm is optimized to find factors of digits or less, so it should factor most numbers of
digits or less (and such numbers will probably only have two prime factors if they are hard to factor).
FactorIntegerECM returns only one factor.
In general, the hardest numbers to factor in a given range are those with two unequal prime factors of about the same size. These numbers can be generated using the built-in function Prime.
In:= Prime[10^7] Prime[10^7+1]
This gives a factor of the previous number.
Here is a fairly large integer.
In:= 2^128 + 1
This took about three and a half hours on a workstation.
The ECM method was discovered and analyzed by H.W. Lenstra. It first appeared as an announcement, "Elliptic Curve Factorization," dated February 14, 1985, and published in H.W. Lenstra, "Factoring Integers with Elliptic Curves," Annals of Mathematics 126 (1987).
This method is a generalization of the factoring algorithm of J. Pollard. The idea is to factor the composite number by generating a random point on a random elliptic curve , and then use the fact that has an algebraic group structure to compute , where is a relatively small integer chosen during the algorithm. If is the identity on the group , where is a prime factor of , then a factorization of is achieved (one has to think of as being reduced ). This can be detected algorithmically, since an illegal inversion must occur (i.e., an illegal use of PowerMod[
a,-1,n] will occur). This happens exactly when the order of the group , where is a prime divisor of , is divisible only by primes less than . This happens in reasonable time because one can choose many curves and the order of the group as varies is well distributed around . This means that it will eventually hit a value that is divisible only by small primes (here is a fixed prime divisor of ).
The original algorithm of Lenstra was mostly of theoretical interest. Many of the implementation ideas are given in Montgomery's paper. The most important point, first suggested by Pollard as an improvement to his method, is to introduce a second stage to the algorithm. The idea is that instead of looking just for numbers with only small factors, one looks for numbers that have all small factors, except for a single large factor. The second stage of the algorithm, therefore, takes the point computed in the first stage and looks to see if any of generate a factorization of . Here are the primes in an interval between and ( in the program). Using the second stage represents an important practical improvement.
Montgomery and others discovered many ways to implement the above efficiently, and the program in the package reflects some of these ideas. An introductory text to this material is D. Bressoud, Factorization and Primality Testing, Springer-Verlag, 1989.
Since the algorithm is quite involved, it is inefficient to use it on numbers that have small factors. These factors can be found more effectively using other techniques, for example, trial division. For this reason, the function FactorIntegerECM[
n] does not perform a complete factorization of but instead returns only a single factor.
The package should therefore be used as a method to find factors of numbers not factored directly by FactorInteger or when only one factor at a time is required, as in the function SquareFreeQ from the package NumberTheory`NumberTheoryFunctions`
Options for FactorIntegerECM.
The options to FactorIntegerECM allow you to vary parameters in the algorithms and to limit to the number of total steps in the algorithm. This allows one to search large numbers for small factors without having to achieve a complete factorization.
The option FactorSize specifies what size of factor you are looking for. When doing general purpose factoring, you usually only want to find any factor of the number . The default is therefore to let FactorSize be about .
The algorithm uses a number of curves in parallel according to the size of the input . The option CurveNumber allows the user to specify how many curves in parallel are used. A value for this option must be a power of 2. The default value of CurveNumber depends on the size of the given number n. For , it is . For , it is . And for , it is .
The advantage of using more curves in parallel is that fewer GCDs are used in stage one of the algorithm and less interpretation overhead occurs in stage two. The disadvantage is that a nontrivial factor found on one curve may have to wait until the algorithm has completed all the curves. The number therefore depends on how many curves one expects to need in total.
The option CurveCountLimit gives an upper bound to the number of curves used in the algorithm. This allows the user to terminate the algorithm before a factor is found. The default is curves (essentially an infinite number).
The program has modest memory requirements. A table of binary digits is set up, as well as a table of