We describe Magma's powerful machinery for the factorization of integers.
In the first subsection the general-purpose Factorization function is described. It employs a combination of methods in an attempt to find the complete prime factorization of a given integer. Some control is possible over each of the methods, but in general default choices for the parameters would give good results for a wide range of arguments.
In the second subsection we decribe functions that enable access to each of the factorization methods available in Magma. The user has control over parameters for these methods.
Factorization functions in Magma return a factorization sequence. This is a sequence of two-element tuples [ <p_1, k_1>, ..., <p_r, k_r>], with p_1<p_2< ... <p_r distinct prime numbers and k_i positive, which is used to represent integers in factored form: n is the product over i of p_i^(k_i). Although such sequences are printed like ordinary sequences, they form a separate category RngIntEltfact. Operations on such factorization sequences are described in the next online help node.
The general Factorization function is designed to give close to optimal performance for the factorization of integers that may be encountered in the course of daily computations. The strategy employed is as follows (the next subsection gives a more detailed description of the individual methods). First of all a compositeness test is used to ensure that the argument is composite; if not the primality proving algorithm is invoked (unless a flag is set to avoid this --- see below). See the previous node for compositeness testing and primality proving. This operation is repeated for any non-trivial factor (and cofactor) found along the way. Before any of the general factorization techniques is employed, it is checked whether |n| is of the special form b^k+-1, in which case an intelligent database look-up is used which is likely to be successful if b and k are not too large. This is equivalent to the Cunningham function on b, k, +-1, described in the next node. In the first true stage of factorization trial division is used to find powers of 2 and other small primes (by default up to 10000). After this it is checked whether the remaining composite number is the power of a positive integer; if so the appropriate root is used henceforth. After this Pollard's rho method is applied (using 8191 iterations by default). The bound on trial division factors and the number of iterations for rho can be set by the optional parameters TrialDivisionLimit and PollardRhoLimit. It is possible, from this point on, that several composite factors still need factorization. The description below applies to each of these.
The final two algorithms deployed are usually indicated by ECM (for Elliptic Curve Method) and MPQS (for Multiple Polynomial Quadratic Sieve). By default, ECM (which is likely to find `smaller' factors if they exist) is used with parameters that depend on the size of the remaining (composite) factors. After that, if a composite factor of at least 25 digits remains, MPQS is used; it is the best method available for factoring integers of more than about 40 decimal digits especially for products of two primes of roughly equal size. If the remaining composite is smaller than 25 digits, ECM is again invoked, now in an indefinite loop until a factor is found. The latter will also occur if the user, via a flag MPQSLimit indicates that MPQS should not be applied to numbers of the given size, and provided the user has not limited the number of ECM trials by setting the ECMLimit. Thus, unless both MPQSLimit and ECMLimit are set as optional parameters by the users, the algorithm will continue until the complete factorization has been completed.
Besides the limiting parameters just mentioned it also possible to avoid the use of primality proofs and receive probable primes, with a flag similar to that used on IsPrime; see the previous node.
A verbose flag can be set to obtain informative printing on progress
in the various stages of factorization. Specific flags for ECM and
MPQS may be used as well; they are described in the next subsection.
SetVerbose("Factorization", v) : MonStgElt, RngIntElt ->
(Procedure.) Set the verbose printing level for all of the factorization algorithms to be v. Currently the legal values for v are true, false, 0 or 1 (false is the same as 0, and true is the same as 1). If the level is 1, information is printed at each stage of the algorithm as a number is factored.
A combination of algorithms (Cunningham, trial division, Pollard rho, ECM and MPQS) is used to attempt to find the complete factorization of |n|, where n is a non-zero integer. A factorization sequence is returned, representing the completely factored part of |n| (which is usually all of |n|). The second return value is 1 or (-1), reflecting the sign of n. If the factorization could not be completed, a third sequence is returned, containing composite factors that could not be decomposed with the given values of the parameters; this can only happen if both ECMLimit and MPQSLimit have been set. (Note that the third variable will remain unassigned if the full factorization is found.)When a very large prime (more than 200 decimal digits say), appears in the factorization, proving its primality may dominate the running time.
There are 6 optional parameters.
Proof: BoolElt Default: true
Bases: RngIntElt Default: 20The parameter Proof (Proof := true by default) can be set to false to indicate that the first sequence may contain probable primes (see also the previous node), in which case the parameter Bases indicates the number of tests used by Miller-Rabin (Bases := 20 by default).
TrialDivisionLimit: RngIntElt Default: 10000The parameter TrialDivisionLimit can be used to specify an upper bound for the primes used in the trial division stage (default TrialDivisionLimit := 10000).
PollardRhoLimit: RngIntElt Default: 8191The parameter PollardRhoLimit can be used to specify an upper bound on the number of iterations in the rho method (default PollardRhoLimit := 8191).
ECMLimit: RngIntElt Default:This optional parameter can be used to limit the number of curves used by the ECM part of the factorization attempt. Setting ECMLimit := 0 prevents the use of ECM. The default value depends on the size of the input, and ranges from 2 for n with less than 37 digits to around 500 for n with 80 digits. The smoothness is incremented in each step to grow by default from 500 to 600 (for 37 digits and less), and from 500 to about 10000 for n having 80 digits. For the indefinite case of ECM (which applies when MPQS is disallowed) the initial smoothness is 500, the number of curves is infinite and the smoothness is incremented by 100 in each step.
MPQSLimit: RngIntElt Default: InfinityThe parameter MPQSLimit can be used specify the maximum number of decimal digits for an integer to which MPQS should still be applied; MPQS will not be invoked on integers having less than (or sometimes equal) 25 decimal digits. Setting the parameter to anything less than 25 will therefore prevent MPQS from being used. Unless ECMLimit has been set, this will imply that ECM will be applied until the full factorization has been obtained.
Note that progress can be monitored by use of Verbose("Factorization", true).
In this node we discuss how various factorization algorithms can be accessed individually. Generally these function should not be used for ordinary factorization (for that use Factorization discussed in the previous node), but they can be used for experimentation, or to build a personal factorization function with control over each of the methods used.
On some functions a little preprocessing is done to ensure that the argument is composite, that powers of 2 (and sometimes 3) are taken out and that the integer to be factored is not the power of an integer.
For each of this functions the Proof (default true) and
Bases parameters can be used to indicate that primality of
prime factors need not be rigorously proved, and how many bases
should be used in the compositeness test, as discussed in the node on IsPrime.
SetVerbose("Cunningham", b) : MonStgElt, Boolean ->
Using this procedure to set either of the verbose flags "Cunningham", "ECM" or "MPQS", (which are false by default) enables the user to obtain progress information on attempts to factor integers using the `Cunningham' method, ECM or MPQS.
This function attempts to factor n=b^k + c, where c in {+-1} and b and k are not too big. This function uses R. Brent's factor algorithm [R.P. Brent and H.J.J. te Riele, Factorizations of a^n +- 1, 13 <= a < 100, Report NM-R9212, Centrum voor Wiskunde en Informatica, Amsterdam, June 1992, 368 pp. ISSN 0169-0388. Updates available by ftp from nimbus.anu.edu.au in the directory pub/Brent.], which employs a combination of table-lookups and attempts at `algebraic' factorization (Aurifeuillian techniques). An error results if the tables, containing most of the known factors for numbers of this form (including the `Cunningham tables'), cannot be located by the system. The function will always return the complete prime factorization (in the form of a factorization sequence) of the number n (but it may take very long before it completes); it should be pointed out, however, that the primes appearing in the factorization are only probable primes and a rigorous primality prover has not been applied.
This attribute is used to change the number of Cunningham factorizations which are stored in Magma. Normally, Magma stores a certain number of factorizations computed by the Cunningham intrinsic function so that commonly needed factorizations can be recalled quickly. When the stored list fills up, the factorization least recently accessed is removed from the list. Setting this attribute to zero ensures that no storage is done. The default value is 20.
Proof: BoolElt Default: true
Bases: RngIntElt Default: 20
The integer n>1 is subjected to trial division by primes up to a certain bound B. If only the argument n is given, B is taken to be 10000. The function returns a factorization sequence and a sequence containing an unfactored composite that remains.
Proof: BoolElt Default: true
Bases: RngIntElt Default: 20
The rho-method of Pollard is invoked by this function to find the factorization of an integer n>1. For this method a quadratic function x^2 + c is iterated k times, with starting value x=s. If only n is used as argument to the function, the default values c=1, s=1, and k=8191 are selected. A speed-up to the original algorithm, due to R.P. Brent footnote{()^ddagger} {R.P. Brent, An improved Monte Carlo factorization algorithm, BIT 20 (1980), 176--184}, is implemented. The function returns two values: a factorization sequence and a sequence containing unfactored composite factors.
Proof: BoolElt Default: true
Bases: RngIntElt Default: 20
Pollard's p - 1 method is used to attempt to factor the integer n>1. For this method a seed s is raised into a very larger power modulo n, the power M consisting of the product of prime powers up to a bound B. In gcd(s^M - 1, n) prime divisors of n will appear that have the property that p - 1 divides M; such primes are called B-smooth. Instead of computing s^M - 1 mod n at once, along the way greatest common divisors are computed for s^(M_i) - 1 mod n and n, where M_i is built up as the product of the first i.w prime powers from the list of those less than B. The bound B, the seed s and the interval w after which common divisors are computed may be specified by the user; alternatively the default values B=100000, s=2, and w=100 will be used.
Proof: BoolElt Default: true
Bases: RngIntElt Default: 20
Use a fast implementation of Shanks's square form factorization method that will only work for integers n>1 less than 2^(2b - 2), where b is the number of bits in a long (which is either 32 or 64). The argument k may be used to specify the maximum number of iterations used to find the square; by default it is 200000.
Proof: BoolElt Default: true
Bases: RngIntElt Default: 20
Given an integer n>1, an attempt to find its prime factorization is made using the Elliptic Curve Method ECM. For at most c randomly chosen elliptic curves E modulo n a large multiple M, built up from the prime powers less than B, of a random point P on E is computed. If a prime divisor p of n has the property that the order of E modulo p divides M (i.e., is B-smooth), then this will be detected as a non-trivial greatest common divisor between n and a coordinate of the point M.P. The initial smoothness bound B, and the maximum number of elliptic curves c may be specified by the user, as well as the growth rate r for the smoothness bound: with each new curve the smoothness is multiplied by r. The rate r must be an integer, rational or real number greater than or equal to 1. If only n is given as argument, default values B=500, r=1.2 and c=10 are used. When a factor is found, the function immediately returns. The function returns three values: a factorization sequence, a sequence containing unfactored composite factors and the number of steps performed.
Proof: BoolElt Default: true
Bases: RngIntElt Default: 20
This function can be used to drive Arjen Lenstra's implementation of the multiple polynomial quadratic sieve MPQS. Given an integer n>5.10^(24) an attempt is made to find the prime factorization of n using MPQS. The name of a directory (which should not yet exist) may be specified as a string D where files used by MPQS will be stored. By default, the directory indicated by the environment variable MAGMA_QS_DIR will be used, and if that has not been set, the directory /tmp. It is possible to assist the master running the main Magma job by generating relations on other machines (slaves), starting an auxiliary process on such machine, in the directory D, by typing magma -q D machine where machine is the name of the machine. The function returns two values: a factorization sequence and a sequence containing unfactored composite factors.
A sequence containing the distinct prime divisors of the positive integer |n|.
Returns a sequence containing all divisors of the positive integer, including 1 and the integer itself. The argument given must be either the integer n itself, or a factorization sequence f representing it.
Given a set or sequence S of integers, return a coprime basis of S in the form of a factorization sequence Q whose integer value is the same as the product of the elements of S but Q has coprime bases (i.e., the first components of tuples from Q are coprime).
> { x : x in [2..1000] | &+Divisors(x) eq 2*x };
{ 6, 28, 496 }
> f := Factorization(496);
> f;
[ <2, 4>, <31, 1> ]
> Divisors(f);
[ 1, 2, 4, 8, 16, 31, 62, 124, 248, 496 ]