2 The General Factorization Routines

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 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| < 10¹², 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 = b^k ±1 for some b, k and looks for factors corresponding to polynomial factors of x^k ±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]