Note that 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).

Divisors(n) : RngIntElt -> [ RngIntElt ]

Returns a sequence containing all divisors of the positive integer n, including 1 and n.

Divisors(s) : [ <RngIntElt, RngIntElt> ] -> [ RngIntElt ]

If n is a positive integer whose prime factorization is given by the factorization sequence, return a sequence containing all of the divisors of n, including 1 and n.

> 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 ]

Factor(n: Al := algorithm) : RngIntElt -> RngIntElt, RngIntElt

Factor(n: Al := algorithm, parameters): RngIntElt -> RngIntElt, RngIntElt

    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.

Factor(n: Al := "Division", parameters) : RngIntElt -> RngIntElt, RngIntElt

    Lower: RngIntElt                    Default: 2

    Upper: RngIntElt                    Default: min(Lower+1000, sqrt{n})

Use trial division, searching for divisors in the interval [( Lower), ( Upper)].

Factor(n: Al := "ECM", parameters) : RngIntElt -> RngIntElt, RngIntElt

    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).

Factor(n: Al := "Fermat", parameters) : RngIntElt -> RngIntElt, RngIntElt

    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).

Factor(n: Al := "Rho", parameters) : RngIntElt -> RngIntElt, RngIntElt

    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.

Factor(n: Al := "pMinus1", parameters) : RngIntElt -> RngIntElt, RngIntElt

    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).

Factor(n: Al := "Shanks", parameters) : RngIntElt -> RngIntElt, RngIntEl

    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).

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 , 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.

Factorization(n: parameters) : RngIntElt -> [ <RngIntElt, RngIntElt> ], RngIntElt, [RngIntElt]

Factorization(n) : RngIntElt -> [ <RngIntElt, RngIntElt> ], RngIntElt

Factorization(n: parameters) : RngIntElt -> [ <RngIntElt, RngIntElt> ], RngIntElt

A combination of algorithms (trial division, Pollard rho, and elliptic curve method) is used to attempt to find the prime power 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), depending 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 7 optional parameters.

    Proof: BoolElt                      Default: true

    Bases: RngIntElt                    Default: 10

The 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).

    Division: RngIntElt                 Default: 1000

The parameter Division can be used to specify an upper bound for the trial division (default Division := 1000).

    Iterations: RngIntElt               Default: 1023

The 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: true

The 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).

PrimeDivisors(n) : RngIntElt -> [RngIntElt]

A sequence containing the distinct prime divisors of the positive integer |n|.