FactInt
  
  
                    Advanced Methods for Factoring Integers
  
  
                                 Version 1.5.2
  
  
                               September 26, 2007
  
  
                                  Stefan Kohl
  
  
  
  Stefan Kohl
      Email:    mailto:kohl@mathematik.uni-stuttgart.de
      Homepage: http://www.cip.mathematik.uni-stuttgart.de/~kohlsn/
      Address:  Institut für Geometrie und Topologie
                Pfaffenwaldring 57
                Universität Stuttgart
                70550 Stuttgart
                Germany
  
  
  
  -------------------------------------------------------
  Abstract
  This  package  for  GAP 4  provides  a general-purpose integer factorization
  routine,  which  makes  use  of  a  combination  of  factoring  methods.  In
  particular it contains implementations of the following algorithms:
  
  --    Pollard's p-1
  
  --    Williams' p+1
  
  --    Elliptic Curves Method (ECM)
  
  --    Continued Fraction Algorithm (CFRAC)
  
  --    Multiple Polynomial Quadratic Sieve (MPQS)
  
  It  also  contains code by Frank Lübeck for making use of Richard P. Brent's
  tables  of  factors  of integers of the form b^k pm 1. FactInt is completely
  written in the GAP language and contains / requires no external binaries. It
  needs  GAPDoc 1.0  [LN07]  or  higher.  FactInt must be installed in the pkg
  subdirectory of the GAP distribution.
  
  
  -------------------------------------------------------
  Copyright
  ©  1999  -  2007  by  Stefan Kohl. This package is distributed under the GNU
  General Public License.
  
  
  -------------------------------------------------------
  Acknowledgements
  I  would  like  to thank Bettina Eick and Steve Linton for their support and
  many interesting discussions.
  
  
  -------------------------------------------------------
  
  
  Content (FactInt)
  
  1. Preface
  2. The General Factorization Routine
    2.1 The method for Factors
      2.1-1 Factors
      2.1-2 FactInt
    2.2 Getting information about the factoring process
      2.2-1 InfoFactInt
  3. The Routines for Specific Factorization Methods
    3.1 Trial division
      3.1-1 FactorsTD
    3.2 Pollard's p-1
      3.2-1 FactorsPminus1
    3.3 Williams' p+1
      3.3-1 FactorsPplus1
    3.4 The Elliptic Curves Method (ECM)
      3.4-1 FactorsECM
    3.5 The Continued Fraction Algorithm (CFRAC)
      3.5-1 FactorsCFRAC
    3.6 The Multiple Polynomial Quadratic Sieve (MPQS)
      3.6-1 FactorsMPQS
  4. How much Time does a Factorization take?
    4.1 Timings for the general factorization routine
    4.2 Timings for the ECM
    4.3 Timings for the MPQS
  
  
  -------------------------------------------------------