gilith/factor

Factoring integers and polynomials

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:

• Number field sieve profile
• Elliptic curve method profile

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