dwww Home | Show directory contents | Find package

  
  
                                    FactInt 
  
  
                    Advanced Methods for Factoring Integers 
  
  
                                     1.6.3
  
  
                                15 November 2019
  
  
                                  Stefan Kohl
  
  
  
  Stefan Kohl
      Email:    mailto:stefan@gap-system.org
      Homepage: https://stefan-kohl.github.io/
  
  -------------------------------------------------------
  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 ± 1. FactInt is completely
  written in the GAP language and contains / requires no external binaries. It
  needs  GAPDoc 1.6  [LN17]  or  higher.  FactInt must be installed in the pkg
  subdirectory of the GAP distribution.
  
  
  -------------------------------------------------------
  Copyright
  © 1999 - 2017 by Stefan Kohl.
  
  FactInt is free software: you can redistribute it and/or modify it under the
  terms  of  the  GNU General Public License as published by the Free Software
  Foundation,  either  version 2 of the License, or (at your option) any later
  version.
  
  FactInt  is  distributed in the hope that it will be useful, but WITHOUT ANY
  WARRANTY;  without  even  the implied warranty of MERCHANTABILITY or FITNESS
  FOR  A  PARTICULAR  PURPOSE.  See  the  GNU  General Public License for more
  details.
  
  For  a  copy  of the GNU General Public License, see the file GPL in the etc
  directory       of       the       GAP       distribution       or       see
  http://www.gnu.org/licenses/gpl.html.
  
  
  -------------------------------------------------------
  Acknowledgements
  I  would  like  to thank Bettina Eick and Steve Linton for their support and
  many interesting discussions.
  
  
  -------------------------------------------------------
  
  
  Contents (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
  
  
  

Generated by dwww version 1.15 on Fri Jun 28 08:38:07 CEST 2024.