Hackage :: [Package]

factor: Factoring integers and polynomials

[ library, mit, number-theory, program ] [ Propose Tags ] [ Report a vulnerability ]

This package contains a reference implementation library of factoring algorithms for integers and univariate polynomials

[Skip to Readme]

Downloads

Maintainer's Corner

Package maintainers

For package maintainers and hackage trustees

Candidates

  • No Candidates
Versions [RSS] 1.0, 1.1, 1.2, 1.3, 1.4, 1.5, 1.6
Dependencies base (>=4.0 && <5.0), containers (>=0.5.7.1), parsec (>=3.1), pretty (>=1.1), random (>=1.0.1.1), time (>=1.6.0.1) [details]
License MIT
Author Joe Leslie-Hurd <joe@gilith.com>
Maintainer Joe Leslie-Hurd <joe@gilith.com>
Category Number Theory
Source repo head: git clone git://github.com/gilith/factor.git
Uploaded by JoeHurd at 2022-06-15T06:13:04Z
Distributions NixOS:1.6
Executables factor
Downloads 976 total (15 in the last 30 days)
Rating (no votes yet) [estimated by Bayesian average]
Your Rating
  • λ
  • λ
  • λ
Status Docs available [build log]
Last success reported on 2022-06-15 [all 1 reports]

Readme for factor-1.6

[back to package description]

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: