**FactInt**

## Advanced Methods for Factoring Integers

Version 1.6.0

December 4, 2017

**
Stefan Kohl
**

Email: 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.