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