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

2 The General Factorization Routine

The FactInt package provides a better method for the operation Factors for integer arguments, which supersedes the one included in the GAP library:

  • Factors( n ) M

    This method returns a sorted list of the prime factors of n.

    If it fails to compute the prime factorization of n, an error is signalled.

    The returned factors pass the built-in probabilistic primality test of GAP (IsProbablyPrimeInt, see the GAP Reference Manual). The same holds for all other factorization routines provided by this package.

    It follows a rough description how FactInt's method for Factors works:

    First of all it checks whether n = bk pm1 for some b, k and looks for factors corresponding to polynomial factors of xk pm1. Provided that b and k are sufficiently small, factors that do not correspond to polynomial factors are taken from Richard P. Brent's Factor Tables Brent04, which are available at

    http://web.comlab.ox.ac.uk/oucl/work/richard.brent/factors.html.

    The code for accessing these tables has been contributed by Frank Lübeck.

    Then the method uses trial division and a number of cheap methods for special cases.

    After the small and other ``easy'' factors have been found this way, FactInt's method searches for ``medium-sized'' factors using Pollard's Rho (by the library function FactorsRho, see the GAP Reference Manual), Pollard's p-1 (see  FactorsPminus1), Williams' p+1 (see  FactorsPplus1) and the Elliptic Curves Method (ECM, see  FactorsECM) in this order.

    If there is still an unfactored part remaining after that, it is factored using the MPQS (see  FactorsMPQS).

    The following options are interpreted:

    TDHints
    A list of additional trial divisors. This is useful only if certain primes p are expected to divide n with probability significantly larger than frac1p.

    RhoSteps
    The number of steps for Pollard's Rho.

    RhoCluster
    The number of steps between two gcd computations in Pollard's Rho.

    Pminus1Limit1 / Pminus1Limit2
    The first- / second stage limit for Pollard's p-1 (see  FactorsPminus1).

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

    Pplus1Limit1 / Pplus1Limit2
    The first- / second stage limit for Williams' p+1 (see  FactorsPplus1).

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

    ECMLimit1 / ECMLimit2
    The initial first- / second stage limit for ECM (see  FactorsECM).

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

    FBMethod
    Specifies which of the factor base methods should be used to do the ``hard work''. Currently implemented: "CFRAC" and "MPQS" (see  FactorsCFRAC,  FactorsMPQS). Default: "MPQS".

    For the use of the GAP Options Stack, see Section Options Stack in the GAP Reference Manual.

    Setting RhoSteps, Pminus1Limit1, Pplus1Residues, Pplus1Limit1, ECMCurves or ECMLimit1 equal to zero switches the respective method off. The method chooses defaults for all option values that are not explicitly set by the user. The option values are also interpreted by the routines for the particular factorization methods described in the next chapter.

    gap> Factors( Factorial(44) + 1 );
    [ 694763, 9245226412016162109253, 413852053257739876455072359 ]
    gap> Factors( 2^997 - 1 );
    [ 167560816514084819488737767976263150405095191554732902607,
      7993430605360222292860936960123884061988016846627213757686887976005930025638\
    602973712891518592878944687759622084106508783413855778177367022158878920741413\
    700868182301410439178049533828082651513160945607018874830040978453228378816647\
    358334681553 ]
    

    The ``working horse'' of this package is

  • FactInt( n ) F

    This function computes the prime factorization of the integer n. The result is returned as a list of two lists. The first list contains the prime factors found, and the second list contains remaining unfactored parts of n, if there are any.

    FactInt interprets all options which are interpreted by the method for Factors described above. In addition, it interprets the options cheap and FactIntPartial. If the option cheap is set, only usually cheap factorization attempts are made. If the option FactIntPartial is set, the factorization process is stopped before invoking the (usually time-consuming) MPQS or CFRAC, if the number of digits of the remaining unfactored part exceeds the bound passed as option value MPQSLimit resp. CFRACLimit.

    Factors( n ) is equivalent to FactInt( n : cheap := false, FactIntPartial := false )[ 1 ].

    gap> FactInt( Factorial(300) + 1 : cheap );
    [ [ 461, 259856122109, 995121825812791, 3909669044842609, 4220826953750952739,
          14841043839896940772689086214475144339 ],
      [ 10483128823176572317398383656043859405333629662907393256352061868792876450\
    580106888272460615410656311193456740818340859600641445970372439235869682208979\
    384309498719255615067943353399357029226058930732298505581697749539842674165663\
    346174704662364145104265524709331550541782037094517458717017420005463846144727\
    565841824785318809625948572758696907279733563594352516014206081210368516157890\
    709802912711149521530885498556124466779020824562030140449992853222252458594688\
    152833725706178959319799211283640357942345263781351 ] ]
    

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

    FactInt manual
    October 2005