We describe Magma's powerful machinery for the factorization of integers.
Several of Magma's factorization functions employ a
factorization sequence. It 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). Operations on such factorization sequences are described
in the next online help node.
SetVerbose("ECM", b) : MonStgElt, Boolean ->
Setting either of the verbose flags "ECM" or "QS", (which are false by default) enables the user to obtain progress information on attempts to factor integers using the elliptic curve or quadratic sieve methods.
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.
> print { x : x in [2..1000] | &+Divisors(x) eq 2*x };
{ 6, 28, 496 }
> f := Factorization(496);
> print f;
[ <2, 4>, <31, 1> ]
> print Divisors(f);
[ 1, 2, 4, 8, 16, 31, 62, 124, 248, 496 ]
Al: MonStgElt Default: "ECM"
Attempt to find a factor of the non-negative integer n, using the algorithm specified by Al, (default "ECM"), with the optional parameters specified below, and return two integer values q and r. If the function succeeds in finding a proper factor, this is returned as the value of q while r returns the quotient n/q. If the algorithm fails to find a factor, then it returns q = 1 and r = n. If it is found that n is a prime then it returns q = n and r = 1.
Lower: RngIntElt Default: 2
Upper: RngIntElt Default: min( L+1000, sqrt{n})
Use trial division, searching for divisors in the interval [L, U], where L and U can be set via Lower and Upper.
Curves: RngIntElt Default: 25
Smoothness: RngIntElt Default: 500
First: RngIntElt Default: 2
Use A.K. Lenstra's implementation of the elliptic curve method for factorization. There are three small optional parameters: Curves, Smoothness and First. These control the number of curves to be tried (default Curves := 25) the smoothness bound (default Smoothness := 500) and a seed for the random number generator (default First := 2).
Lower: RngIntElt Default: 17
Upper: RngIntElt Default: sqrt{n}
Use a modular version of the Fermat method. In this method one attempts to write to factor n by representing it as a difference of squares, n = y^2 - x^2=(y - x)(y + x). With the optional parameters Lower and Upper the user may specify bounds on the smaller factor y - x; by default the lower bound is Lower := 17 and the upper bound Upper := sqrt n. (Factors up to 17 are found first by trial division).
Use Arjen Lenstra's implementation of the (double prime version of) the multiple polynomial quadratic sieve.
Constant: RngIntElt Default: 1
First: RngIntElt Default: 1
Iterations: RngIntElt Default: -1
Use Pollard's rho method. The polynomial used is of the form x^2 + c, with c a small integer that is 1 by default but can be modified by setting the optional parameter Constant. Also, the starting value (default 1) can be controlled, using the optional parameter First, and the number of iterations can be limited with Iterations; its default is Limit := -1, meaning no limit.
Max: RngIntElt Default: 100000
Base: RngIntElt Default: 2
Length: RngIntElt Default: 100
Use Pollard's p - 1 method. There are 3 optional parameters. Parameter Max (default Max := 100000) controls the bound on the primes in the factor basis, using Base it is possible to change the starting value (default Base := 2) and Length may be used to change the fixed interval after which greatest common divisors are calculated (default Length := 100).
Iterations: RngIntElt Default: 10000000
Use Shanks's square form factorization method. The small optional parameter Limit can be used to limit the number of iterations in the loop to find the square in the continued fraction expansion (default Limit := 10000000).
Use an alternative (fast) implementation of Shanks's square form factorization method that will only work for integers n less than 2^(2b - 2), where b is the number of bits in a long (which is either 32 or 64).
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.
A combination of algorithms (trial division, Pollard rho, elliptic curve method, and quadratic sieve) 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 on 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.Before any of the general factorization techniques is employed, it is checked whether |n| is of the form b^k+-1, in which case the Cunningham function is invoked on b, k, +-1; note however that in this case the primes in the factorization sequence are proven to be prime, unless the flag Proof described below is set to false. When very large primes appear in the factorization, proving their primality may dominate the running time.
There are 9 optional parameters.
Proof: BoolElt Default: true
Bases: RngIntElt Default: 10The parameter Proof (Proof := true by default) can be set to false to indicate that the first sequence may contain probable primes (see the previous section), in which case the parameter Bases indicates the number of Miller-Rabin test to be used (Bases := 10 by default).
Upper: RngIntElt Default: 1000The parameter Upper can be used to specify an upper bound for the trial division (default Upper := 1000).
Iterations: RngIntElt Default: 1023The parameter Iterations can be used to specify an upper bound on the number of iterations in the rho method (default Iterations := 1023).
Curves: RngIntElt Default: 10
Smoothness: RngIntElt Default: 500
Continue: BoolElt Default: trueThe parameters Curves and Smoothness can be used to control the number of curves (default 10) and the smoothness bound (default 500, but incremented by 100 for every subsequent curve) in the elliptic curve method. Finally, by putting Continue := true one may indicate that if the factorization has not been completed yet, a final attempt using the elliptic curve method with "optimal" parameters should be made (this may be very time consuming).
ECMOnly: BoolElt Default: false
QSOnly: BoolElt Default: falseThe parameters ECMOnly and QSOnly are provided for some control over the hard part of the factorization. By setting ECMOnly true the use of the quadratic sieve is avoided (which is important if heavy use of temporary file space is to be avoided). Similarly, by setting QSOnly, the use of the elliptic curve algorithm is avoided. By default, after the initial factorization attempts (trial division, Pollard) have not succeeded entirely, ECM is invoked with small bound and few curves (10), then the quadratic sieve.
Note that progress can be monitored by use of the Verbose flags.
This function can be used to drive Arjen Lenstra's implementation of the multiple polynomial quadratic sieve. Given an integer n and a string D giving the name of a directory, an attempt is made to find the prime factorization of n, using files in the directory D. 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 a sequence of prime factors found as a cofactor.[Next] [Prev] [Right] [Left] [Up] [Index] [Root]