  
  [1X2 [33X[0;0YThe General Factorization Routine[133X[101X
  
  
  [1X2.1 [33X[0;0YThe method for [10XFactors[110X[101X[1X[133X[101X
  
  [33X[0;0YThe  [5XFactInt[105X  package provides a better method for the operation [10XFactors[110X for
  integer arguments, which supersedes the one included in the [5XGAP[105X Library:[133X
  
  [1X2.1-1 Factors[101X
  
  [33X[1;0Y[29X[2XFactors[102X( [3Xn[103X ) [32X method[133X
  [6XReturns:[106X  [33X[0;10Ya sorted list of the prime factors of [3Xn[103X.[133X
  
  [33X[0;0YThe  returned  factors pass the built-in probabilistic primality test of [5XGAP[105X
  ([10XIsProbablyPrimeInt[110X,  Baillie-PSW  Primality  Test;  see  the  [5XGAP[105X Reference
  Manual).  If  the  method  fails to compute the prime factorization of [3Xn[103X, an
  error  is  signalled.  The  same  holds for all other factorization routines
  provided  by  this  package. The following is a rough description of how the
  factorization method works:[133X
  
  [33X[0;0YFirst  of all, the method checks whether [22Xn = b^k ± 1[122X for some [22Xb[122X, [22Xk[122X and looks
  for  factors corresponding to polynomial factors of [22Xx^k ± 1[122X. Provided that [22Xb[122X
  and  [22Xk[122X  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.[133X
  
  [33X[0;0YThese tables are nowadays maintained by Jonathan Crombie, and have grown far
  too  large  to  be  distributed  in full. The subset shipped with [5XFactInt[105X is
  determined  as  follows: for a base [22Xb[122X and an exponent [22Xk[122X, all currently known
  factors  of  [22Xb^k  ±  1[122X  are  included  if  [22Xb  ≤ 100[122X, or if [22Xb[122X is a prime less
  than 1000,  or  if  the  pair  [22X(b,k)[122X  was  already  covered  by  the  tables
  distributed with [5XFactInt[105X 1.6.3. In particular, everything that was available
  in  earlier  versions  of  [5XFactInt[105X  is  still  available, in many cases with
  additional factors.[133X
  
  [33X[0;0YUsers  who need factors beyond this range can replace the distributed tables
  by  the  full  collection using the undocumented function [10XFetchBrentFactors[110X;
  see  the  comments  in  [11Xlib/general.gi[111X.  This  requires  write access to the
  [5XFactInt[105X  installation  directory  as  well as the external programs [10Xcurl[110X and
  [10Xgzip[110X.[133X
  
  [33X[0;0YThen  the  method  uses  trial  division  and  a number of cheap methods for
  various  common  special  cases. After the small and other [21Xeasy[121X factors have
  been  found  this  way,  [5XFactInt[105X's  method searches for [21Xmedium-sized[121X factors
  using  Pollard's  Rho  (by  the  library  function  [10XFactorsRho[110X,  see the [5XGAP[105X
  Reference Manual), Pollard's [22Xp-1[122X (see [2XFactorsPminus1[102X ([14X3.2-1[114X)), Williams' [22Xp+1[122X
  (see [2XFactorsPplus1[102X   ([14X3.3-1[114X))   and   the   Elliptic   Curves  Method  (ECM,
  see [2XFactorsECM[102X ([14X3.4-1[114X)) in this order.[133X
  
  [33X[0;0YIf  there  is  still an unfactored part remaining after that, it is factored
  using   the  Multiple  Polynomial  Quadratic  Sieve  (MPQS,  see [2XFactorsMPQS[102X
  ([14X3.6-1[114X)).[133X
  
  [33X[0;0YThe following options are interpreted:[133X
  
  [8X[3XTDHints[103X[8X[108X
        [33X[0;6YA  list  of  additional trial divisors. This is useful only if certain
        primes [22Xp[122X  are  expected  to  divide  [22Xn[122X  with probability significantly
        larger than [22Xfrac1p[122X.[133X
  
  [8X[3XRhoSteps[103X[8X[108X
        [33X[0;6YThe number of steps for Pollard's Rho.[133X
  
  [8X[3XRhoCluster[103X[8X[108X
        [33X[0;6YThe number of steps between two gcd computations in Pollard's Rho.[133X
  
  [8X[3XPminus1Limit1[103X[8X / [3XPminus1Limit2[103X[8X[108X
        [33X[0;6YThe  first- / second stage limit for Pollard's [22Xp-1[122X (see [2XFactorsPminus1[102X
        ([14X3.2-1[114X)).[133X
  
  [8X[3XPplus1Residues[103X[8X[108X
        [33X[0;6YThe number of residues to be tried by Williams' [22Xp+1[122X (see [2XFactorsPplus1[102X
        ([14X3.3-1[114X)).[133X
  
  [8X[3XPplus1Limit1[103X[8X / [3XPplus1Limit2[103X[8X[108X
        [33X[0;6YThe  first-  / second stage limit for Williams' [22Xp+1[122X (see [2XFactorsPplus1[102X
        ([14X3.3-1[114X)).[133X
  
  [8X[3XECMCurves[103X[8X[108X
        [33X[0;6YThe  number  of  elliptic  curves  to  be tried by the Elliptic Curves
        Method  (ECM)  (see [2XFactorsECM[102X  ([14X3.4-1[114X)).  Also admissible: a function
        that  takes the number [22Xn[122X to be factored as an argument and returns the
        desired number of curves to be tried.[133X
  
  [8X[3XECMLimit1[103X[8X / [3XECMLimit2[103X[8X[108X
        [33X[0;6YThe  initial  first-  /  second  stage  limit  for ECM (see [2XFactorsECM[102X
        ([14X3.4-1[114X)).[133X
  
  [8X[3XECMDelta[103X[8X[108X
        [33X[0;6YThe  increment  per curve for the first stage limit in ECM. The second
        stage limit is adjusted appropriately (see [2XFactorsECM[102X ([14X3.4-1[114X)).[133X
  
  [8X[3XECMDeterministic[103X[8X[108X
        [33X[0;6YIf  true,  ECM  chooses  its curves deterministically, i.e. repeatable
        (see [2XFactorsECM[102X ([14X3.4-1[114X)).[133X
  
  [8X[3XFBMethod[103X[8X[108X
        [33X[0;6YSpecifies  which  of  the factor base methods should be used to do the
        [21Xhard work[121X. Currently implemented: [10X"CFRAC"[110X and [10X"MPQS"[110X (see [2XFactorsCFRAC[102X
        ([14X3.5-1[114X) and [2XFactorsMPQS[102X ([14X3.6-1[114X), respectively). Default: [10X"MPQS"[110X.[133X
  
  [33X[0;0YFor  the  use of the [5XGAP[105X Options Stack, see Chapter [13XOptions Stack[113X in the [5XGAP[105X
  Reference Manual.[133X
  
  [33X[0;0YSetting  [3XRhoSteps[103X, [3XPminus1Limit1[103X, [3XPplus1Residues[103X, [3XPplus1Limit1[103X, [3XECMCurves[103X or
  [3XECMLimit1[103X  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.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XFactors( Factorial(44) + 1 );[127X[104X
    [4X[28X[ 694763, 9245226412016162109253, 413852053257739876455072359 ][128X[104X
    [4X[25Xgap>[125X [27XFactors( 2^997 - 1 );[127X[104X
    [4X[28X[ 167560816514084819488737767976263150405095191554732902607, [128X[104X
    [4X[28X  79934306053602222928609369601238840619880168466272137576868879760059\[128X[104X
    [4X[28X3002563860297371289151859287894468775962208410650878341385577817736702\[128X[104X
    [4X[28X2158878920741413700868182301410439178049533828082651513160945607018874\[128X[104X
    [4X[28X830040978453228378816647358334681553 ][128X[104X
  [4X[32X[104X
  
  [33X[0;0YThe  above  method  for  [10XFactors[110X  calls the following function, which is the
  actual [21Xworkhorse[121X of this package:[133X
  
  [1X2.1-2 FactInt[101X
  
  [33X[1;0Y[29X[2XFactInt[102X( [3Xn[103X ) [32X function[133X
  [6XReturns:[106X  [33X[0;10Ya  list of two lists, where the first list contains the determined
            prime  factors  of [3Xn[103X  and  the  second list contains the remaining
            unfactored parts of [3Xn[103X, if there are any.[133X
  
  [33X[0;0YThis function interprets all options which are interpreted by the method for
  [10XFactors[110X  described  above.  In addition, it interprets the options [3Xcheap[103X and
  [3XFactIntPartial[103X. If the option [3Xcheap[103X is set, only usually cheap factorization
  attempts  are  made.  If the option [3XFactIntPartial[103X 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 [3XMPQSLimit[103X or [3XCFRACLimit[103X, respectively.[133X
  
  [33X[0;0Y[10XFactors([3Xn[103X[10X)[110X        is       equivalent       to       [10XFactInt([3Xn[103X[10X:[3Xcheap[103X[10X:=false,
  [3XFactIntPartial[103X[10X:=false)[1][110X.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XFactInt( Factorial(300) + 1 : cheap );[127X[104X
    [4X[28X[ [ 461, 259856122109, 995121825812791, 3909669044842609, [128X[104X
    [4X[28X      4220826953750952739, 14841043839896940772689086214475144339 ], [128X[104X
    [4X[28X  [ 104831288231765723173983836560438594053336296629073932563520618687\[128X[104X
    [4X[28X9287645058010688827246061541065631119345674081834085960064144597037243\[128X[104X
    [4X[28X9235869682208979384309498719255615067943353399357029226058930732298505\[128X[104X
    [4X[28X5816977495398426741656633461747046623641451042655247093315505417820370\[128X[104X
    [4X[28X9451745871701742000546384614472756584182478531880962594857275869690727\[128X[104X
    [4X[28X9733563594352516014206081210368516157890709802912711149521530885498556\[128X[104X
    [4X[28X1244667790208245620301404499928532222524585946881528337257061789593197\[128X[104X
    [4X[28X99211283640357942345263781351 ] ][128X[104X
  [4X[32X[104X
  
  
  [1X2.2 [33X[0;0YGetting information about the factoring process[133X[101X
  
  [33X[0;0YOptionally,  the  [5XFactInt[105X  package prints information on the progress of the
  factorization process:[133X
  
  [1X2.2-1 InfoFactInt[101X
  
  [33X[1;0Y[29X[2XInfoFactInt[102X [32X info class[133X
  [33X[1;0Y[29X[2XFactIntInfo[102X( [3Xlevel[103X ) [32X function[133X
  
  [33X[0;0YThis  Info  class  makes  it  possible  to  monitor  what happens during the
  factoring process.[133X
  
  [33X[0;0YIf  [10XInfoLevel(InfoFactInt)  =  1[110X, then basic information about the factoring
  techniques   used   is  displayed.  If  this  InfoLevel  has  value 2,  then
  additionally  all  [21Xrelevant[121X 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.[133X
  
  [33X[0;0YEnter [10XFactIntInfo([3Xlevel[103X[10X)[110X to set the [10XInfoLevel[110X of [10XInfoFactInt[110X to the positive
  integer    [3Xlevel[103X.    The   call   [10XFactIntInfo([3Xlevel[103X[10X);[110X   is   equivalent   to
  [10XSetInfoLevel(InfoFactInt,[3Xlevel[103X[10X);[110X.[133X
  
  [33X[0;0YThe  informational  output  is  usually  not  literally  the  same  in  each
  factorization  attempt  for  a  given  integer  with given parameters. For a
  description  of  the  Info  mechanism, see Section [13XInfo Functions[113X in the [5XGAP[105X
  Reference Manual.[133X
  
