The factor package is a Haskell library for factoring integers
and polynomials, implementing the following algorithms:

- Number field sieve (NFS) for factoring arbitrary integers
- Elliptic curve method (ECM) for finding "small" factors of integers
- Miller-Rabin probabilistic primality test for integers
- Berlekamp-Zassenhaus algorithm for factoring integer polynomials
- Berlekamp algorithm for factoring polynomials over GF(
*p*) (for small primes *p*)
- Cantorâ€“Zassenhaus algorithm for factoring polynomials over GF(
*p*) (for arbitrary odd primes *p*)

This software is released under the MIT License.

## Install

Installing the factor package requires cabal:

```
git clone https://github.com/gilith/factor.git
cd factor
cabal install --enable-tests
```

The factor package contains an executable called `factor`

, which is
run as follows:

```
Usage: factor [options] "expression to factor"
--trial=N Set trial division maximum to N
--ecm-primes=N Limit ECM to first N primes (use - for no limit)
--nfs-chars=N Use N quadratic characters in NFS
--nfs-verbose Show complete lists in NFS verbose messages
-v --verbose Enable verbose messages
-t --timestamp Prepend verbose messages with timestamp
--version Print version
-h --help Show help
```

Example input expressions:

```
2047 Concrete integer
2^2^7 + 1 Integer expression
N[100] Random 100-bit positive integer
P[50] * P[50] Product of random 50-bit primes
x^4 - 10*x^2 + 1 Polynomial over the integers
x^5^2 - x (mod 5) Polynomial over GF(5)
```

Let expressions are supported: `let p = P[4] in x^p - x (mod p)`

Multivariate polynomials (e.g., `y^2 - x^3 - a*x - b`

) are not supported

## Test and Profile

Use cabal to run the test suite:

```
cabal test
```

Profiles of the time and memory requirements for factoring inputs of
various sizes:

The following recipe can be used to visualize the dynamic memory
usage of the number field sieve:

```
cabal clean
cabal configure --enable-profiling
cabal build
factor +RTS -hc -RTS -v --ecm-primes 0 'P[35] * P[35]'
hp2ps -e8in -c factor.hp
gm convert -density 180 factor.ps factor.png
xview factor.png
```

## References

Comments in the code contain references to descriptions of the
specific implemented algorithms, and the following references helped
with general understanding of the number field sieve:

- A Tale of Two Sieves, Carl Pomerance, 1996
- The Number Field Sieve, Steven Byrnes, 2005
- An Introduction to the General Number Field Sieve, Matthew E Briggs, 1998
- Integer Factorization, Per Leslie Jensen, 2005
- Square Root Algorithms for the Number Field Sieve, Emmanuel Thome, 2012
- MSIEVE: A Library for Factoring Large Integers, Jason Papadopoulos, 2010