2. The General Factorization Routine
  
  
  2.1 The method for Factors
  
  The  FactInt  package provides a better method for the operation Factors for
  integer arguments, which supersedes the one included in the GAP Library:
  
  2.1-1 Factors
  
  > Factors( n ) _______________________________________________________method
  Returns:  A sorted list of the prime factors of n.
  
  The  returned  factors pass the built-in probabilistic primality test of GAP
  (IsProbablyPrimeInt,  Baillie-PSW  Primality  Test;  see  the  GAP Reference
  Manual).  If  the  method  fails to compute the prime factorization of n, an
  error  is  signalled.  The  same  holds for all other factorization routines
  provided   by   this  package.  It  follows  a  rough  description  how  the
  factorization method works:
  
  First of all, the method checks whether n = b^k pm 1 for some b, k and looks
  for factors corresponding to polynomial factors of x^k pm 1. Provided that b
  and  k  are  not too large, the factors that do not correspond to polynomial
  factors  are  taken  from Richard P. Brent's Factor Tables [Bre04]. 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
  various  common 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 (3.2-1)), Williams' p+1
  (see FactorsPplus1   (3.3-1))   and   the   Elliptic   Curves  Method  (ECM,
  see FactorsECM (3.4-1)) in this order.
  
  If  there  is  still an unfactored part remaining after that, it is factored
  using   the  Multiple  Polynomial  Quadratic  Sieve  (MPQS,  see FactorsMPQS
  (3.6-1)).
  
  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
        (3.2-1)).
  
  Pplus1Residues
        The number of residues to be tried by Williams' p+1 (see FactorsPplus1
        (3.3-1)).
  
  Pplus1Limit1 / Pplus1Limit2
        The  first-  / second stage limit for Williams' p+1 (see FactorsPplus1
        (3.3-1)).
  
  ECMCurves
        The  number  of  elliptic  curves  to  be tried by the Elliptic Curves
        Method  (ECM)  (see FactorsECM  (3.4-1)).  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
        (3.4-1)).
  
  ECMDelta
        The  increment  per curve for the first stage limit in ECM. The second
        stage limit is adjusted appropriately (see FactorsECM (3.4-1)).
  
  ECMDeterministic
        If  true,  ECM  chooses  its curves deterministically, i.e. repeatable
        (see FactorsECM (3.4-1)).
  
  FBMethod
        Specifies  which  of  the factor base methods should be used to do the
        "hard    work".    Currently    implemented:    "CFRAC"   and   "MPQS"
        (see FactorsCFRAC   (3.5-1)  and FactorsMPQS  (3.6-1),  respectively).
        Default: "MPQS".
  
  For  the  use of the GAP Options Stack, see Chapter 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.
  
  ---------------------------  Example  ----------------------------
    
    gap> Factors( Factorial(44) + 1 );
    [ 694763, 9245226412016162109253, 413852053257739876455072359 ]
    gap> Factors( 2^997 - 1 );
    [ 167560816514084819488737767976263150405095191554732902607, 
      79934306053602222928609369601238840619880168466272137576868879760059\
    3002563860297371289151859287894468775962208410650878341385577817736702\
    2158878920741413700868182301410439178049533828082651513160945607018874\
    830040978453228378816647358334681553 ]
    
  ------------------------------------------------------------------
  
  The  above  method  for  Factors  calls the following function, which is the
  actual "working horse" of this package:
  
  2.1-2 FactInt
  
  > FactInt( n ) _____________________________________________________function
  Returns:  A  list of two lists, where the first list contains the determined
            prime  factors  of n  and  the  second list contains the remaining
            unfactored parts of n, if there are any.
  
  This function 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 or CFRACLimit, respectively.
  
  Factors(n)        is       equivalent       to       FactInt(n:cheap:=false,
  FactIntPartial:=false)[1].
  
  ---------------------------  Example  ----------------------------
    
    gap> FactInt( Factorial(300) + 1 : cheap );
    [ [ 461, 259856122109, 995121825812791, 3909669044842609, 
          4220826953750952739, 14841043839896940772689086214475144339 ], 
      [ 104831288231765723173983836560438594053336296629073932563520618687\
    9287645058010688827246061541065631119345674081834085960064144597037243\
    9235869682208979384309498719255615067943353399357029226058930732298505\
    5816977495398426741656633461747046623641451042655247093315505417820370\
    9451745871701742000546384614472756584182478531880962594857275869690727\
    9733563594352516014206081210368516157890709802912711149521530885498556\
    1244667790208245620301404499928532222524585946881528337257061789593197\
    99211283640357942345263781351 ] ]
    
  ------------------------------------------------------------------
  
  
  2.2 Getting information about the factoring process
  
  Optionally,  the  FactInt  package prints information on the progress of the
  factorization process:
  
  2.2-1 InfoFactInt
  
  > InfoFactInt_____________________________________________________info class
  > FactIntInfo( level ) _____________________________________________function
  
  This Info class allows to monitor what happens during the factoring process.
  
  If  InfoLevel(InfoFactInt)  =  1, then basic information about the factoring
  techniques   used   is  displayed.  If  this  InfoLevel  has  value 2,  then
  additionally all "relevant" steps in the factoring algorithms are mentioned.
  If  it  is  set equal to 3, then large amounts of details of the progress of
  the factoring process are shown.
  
  Enter FactIntInfo(level) to set the InfoLevel of InfoFactInt to the positive
  integer    level.    The   call   FactIntInfo(level);   is   equivalent   to
  SetInfoLevel(InfoFactInt,level);.
  
  The  informational  output  is  usually  not  literally  the  same  in  each
  factorization  attempt  to  a  given  integer  with  given parameters. For a
  description  of  the  Info  mechanism, see Section Info Functions in the GAP
  Reference Manual.