[1X[5XFactInt[0X[0X [1XAdvanced Methods for Factoring Integers[0X Version 1.5.2 September 26, 2007 Stefan Kohl Stefan Kohl Email: [7Xmailto:kohl@mathematik.uni-stuttgart.de[0X Homepage: [7Xhttp://www.cip.mathematik.uni-stuttgart.de/~kohlsn/[0X Address: Institut für Geometrie und Topologie Pfaffenwaldring 57 Universität Stuttgart 70550 Stuttgart Germany ------------------------------------------------------- [1XAbstract[0X This package for [5XGAP[0X 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. [5XFactInt[0X is completely written in the [5XGAP[0X language and contains / requires no external binaries. It needs [5XGAPDoc[0X 1.0 [LN07] or higher. [5XFactInt[0X must be installed in the [11Xpkg[0X subdirectory of the [5XGAP[0X distribution. ------------------------------------------------------- [1XCopyright[0X © 1999 - 2007 by Stefan Kohl. This package is distributed under the GNU General Public License. ------------------------------------------------------- [1XAcknowledgements[0X I would like to thank Bettina Eick and Steve Linton for their support and many interesting discussions. ------------------------------------------------------- [1XContent (FactInt)[0X 1. Preface 2. The General Factorization Routine 2.1 The method for [10XFactors[0X 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 -------------------------------------------------------