[Up] [Previous] [Next] [Index]

# 2 The General Factorization Routines

## 2.1 If you do not care about the methods used

• `IntegerFactorization( `n` ) F`

`IntegerFactorization` computes the prime factorization of the integer n. The result is returned as a list of the prime factors. In case of failure an error is signalled.

The returned factors are considered to be prime by the built-in probabilistic primality test of GAP (`IsProbablyPrimeInt`, see the Reference Manual), as in all other factorization routines included in this package.

`IntegerFactorization( n )` is equivalent to `FactInt( n : FactIntPartial:=false )[ 1 ]` (see  FactInt).

`IntegerFactorization` is also installed as a method for `Factors`, with a higher value than the GAP library function `FactorsInt`.

```gap> IntegerFactorization( Factorial(24) - 1 );
[ 625793187653, 991459181683 ]
```
```gap> Factors( 1459^24 - 1 );
[ 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 5, 7, 13, 73, 97, 193, 283, 337, 1009,
303889, 669433, 1064341, 6722971513, 4531280671081, 313380751265929 ]
```

## 2.2 Taking influence on the methods being used

• `FactInt( `n` ) F`

`FactInt` computes the prime factorization of the integer n. The result is returned as a list of two lists, where the first one contains the prime factors found, and the second one contains remaining unfactored parts of n, if there are any (if FactIntPartial not set, this should never happen, because in this case the function does not return before n is factored completely).

The factors returned as prime factors are considered to be prime by the build-in probabilistic primality test of GAP (`IsProbablyPrimeInt`, see the Reference Manual). This also applies to all other factorization routines provided by this package.

`FactInt` recognizes the following options:

TDHints
specifies a list of additional trial divisors (when factoring ``random'' numbers, giving a large list of trial divisors here is certainly not a sensible approach, TDHints is useful only if certain primes p are expected to divide n with probability significantly larger than [ 1/(p)])

RhoSteps
specifies the number of steps for Pollard's Rho,

RhoCluster
specifies the number of steps between two Gcd computations in Pollard's Rho

Pminus1Limit1
specifies the first stage limit for Pollard's p-1 (see  FactorsPminus1)

Pminus1Limit2
specifies the second stage limit for Pollard's p-1 (see  FactorsPminus1)

Pplus1Residues
specifies the number of residues to be tried by Williams' p+1 (see  FactorsPplus1)

Pplus1Limit1
specifies the first stage limit for Williams' p+1 (see  FactorsPplus1)

Pplus1Limit2
specifies the second stage limit for Williams' p+1 (see  FactorsPplus1)

ECMCurves
specifies the number of elliptic curves to be tried by the Elliptic Curves Method (ECM) (see  FactorsECM), also admissible: a function that takes an argument n (the number to be factored) and returns the desired number of curves to be tried

ECMLimit1
specifies the initial first stage limit for ECM (see  FactorsECM)

ECMLimit2
specifies the initial second stage limit for ECM (see  FactorsECM)

ECMDelta
specifies the increment per curve for the first stage limit in ECM, the second stage limit is adjusted appropriately (see  FactorsECM)

ECMDeterministic
if true, ECM chooses its curves deterministically, i.e. repeatable (see  FactorsECM)

FactIntPartial
if true, the partial factorization obtained by applying the factoring methods whose time complexity depends mainly on the size of the factors to be found and less on the size of n (those of the first class mentioned in the preface) is returned and the factor base methods (MPQS and CFRAC) are not used to complete the factorization for numbers that exceed the bound given by CFRACLimit resp. MPQSLimit; default: false

FBMethod
specifies which of the factor base methods should be used to do the ``hard work''; currently implemented: CFRAC and MPQS (see  FactorsCFRAC,  FactorsMPQS)

CFRACLimit
specifies the maximal number of decimal digits of an integer to which the Continued Fraction Algorithm (CFRAC) should be applied (only used when FactIntPartial = true) (see  FactorsCFRAC)

MPQSLimit
as above, for the Multiple Polynomial Quadratic Sieve (MPQS) (see  FactorsMPQS)

Once these option values are set by the user via `PushOptions`, all subsequent factorizations by `FactInt` and `IntegerFactorization` (see  IntegerFactorization) are done using these settings without the need to give further arguments (in respect to the use of the GAP Options Stack, see the Reference Manual). Setting RhoSteps, Pminus1Limit1, Pplus1Residues, Pplus1Limit1, ECMCurves or ECMLimit1 to zero switches the respective method off. `FactInt` chooses defaults for all option values that are not explicitly set by the user. The option values are also taken into consideration by the routines for the particular factorization methods described in the next chapter when default values have to be chosen.

If |n| < 1012, `FactInt` just calls the library function `FactorsInt`, which is guaranteed to give the correct result for numbers in this range. If not, it checks whether n = bk ±1 for some b, k and looks for factors corresponding to polynomial factors of xk ±1 (in order to immediately obtain factors that do not correspond to polynomial factors it is necessary to give a list of the prime factors of numbers of this form as TDHints).

As the first general factorization step, `FactInt` does trial division by the primes below 1000. After that, it checks whether the remaining part of the number to be factored already is a prime. If not, it does trial divisions by some already known primes, using the list `Primes2` (see GAP-Manual). If there is still an unfactored part m, then it checks whether m is a non-trivial power of an integer. Then, the additional list of trial divisors given as TDHints is processed, if present.

After the small and other ``easy'' factors have been casted out this way, `FactInt` searches for ``medium-sized'' factors using Pollard's Rho (by the library function `FactorsRho`, see GAP-Manual), Pollard's p-1 (see  FactorsPminus1), Williams' p+1 (see  FactorsPplus1) and the Elliptic Curves Method (ECM, see  FactorsECM) in this order. After that, if there is still an unfactored part remaining and FactIntPartial = false (or the remaining composites do not exceed the bound given by CFRACLimit resp. MPQSLimit), one of the factor base methods (CFRAC, see  FactorsCFRAC or MPQS, see  FactorsMPQS) is used to do the ``hard work'', depending on the value of FBMethod, which could be `"MPQS"` or `"CFRAC"`.

Finally, it is checked whether the product of all factors is equal to n and whether all factors in the first list of the result pass the GAP pseudoprime test `IsProbablyPrimeInt` and all factors in the second list are really composites. These checks are also done by all other factorization routines provided by this package.

```gap> FactInt( Factorial(39) + 1 : RhoSteps := 16384, Pminus1Limit1 := 100000,
Pplus1Limit1 := 2000, ECMLimit1 := 5000, ECMCurves := 10,
FBMethod := "MPQS" );
[ [ 79, 57554485363, 146102648914939, 30705821478100704367 ], [  ] ]
```

[Up] [Previous] [Next] [Index]

FactInt manual
May 2002