Advanced Methods for *Fact*oring
*Int*egers

Version 1.5.4

Stefan Kohl

FactInt is a GAP 4 package which provides implementations of the following methods for factoring integers:

- Pollard's
*p*-1 - Williams'
*p*+1 - Elliptic Curves Method (ECM)
- Continued Fraction Algorithm (CFRAC)
- Multiple Polynomial Quadratic Sieve (MPQS)

FactInt also makes use of
Richard P. Brent's tables
of known factors of integers of the form *b ^{k}+/-1* for `small'

The ECM is suited best for finding factors which are neither too small
(i.e. have less than about 12 decimal digits) nor too close to the square root
of the number to be factored.
The MPQS is designed for factoring products of two primes of comparable orders
of magnitude. CFRAC is the historical predecessor of the MPQS.
Pollard's *p*-1 and Williams' *p*+1 are useful for finding factors
*p* such that all prime factors of *p*-1 resp. *p*+1 are
`small', e.g. smaller than 1000000.
All factoring methods implemented in this package are probabilistic.
In particular the time needed by the ECM depends highly on the actual - good
or bad - luck.

FactInt provides a general-purpose factorization routine which uses an appropriate combination of the methods mentioned above, the Pollard Rho routine which is implemented in the GAP Library and a variety of tricks for special cases to obtain a good average performance for `arbitrary' integers. At the user's option, FactInt provides detailed information about the progress of the factorization process.

FactInt is published / redistributed on the GAP website here.

- Download FactInt:
- factint-1.5.4.tar.gz (current version, released 13-Feb-2017, about 3.8 MB).
- factint-1.5.3-win.zip (previous version, released 16-Jun-2011, about 4.2 MB).
- factint-1.5.2.tar.gz (old version, released 26-Sep-2007, about 3.2 MB).

- FactInt can be used under any operating system for which GAP is available.
- Requirements: GAP 4.4.9 or newer and GAPDoc 1.0 or newer.
- Installation: extract the distribution file in the
`pkg/`

subdirectory of the GAP root directory. - Manual: HTML PDF.
- Some examples for the use of FactInt.
- Version history: see CHANGES.
- A readme file which provides similar information as given on this webpage.
- GAP - readable package information: see PackageInfo.g.
- Slides I used in my talk at the GAP workshop in April 1999 in Linz: slides.zoo (26K).

If you have problems with this package, wish to make comments or suggestions, or if you find bugs, please send e - mail to Stefan Kohl.

Back to main page | Last modified: 24-Feb-2017 |