FLINT: Fast Library for Number Theory

FLINT is a C library for doing number theory, written by William Hart and David Harvey.

Download FLINT

11-Mar-08 FLINT 1.0.9 is released!!

The tarball flint-1.0.9.tar.gz is now available.

FLINT Documentation

The documentation for FLINT 1.0.9 is available in the release tarball, or it can be downloaded here, flint-1.0.9.pdf.

Development version (not stable)

15-Mar-08 FLINT 1.1-devel

The tarball flint-1.1-devel.tar.gz is available.

The documentation for FLINT 1.1-devel is available here, flint-1.1.pdf.

Contributors

International Colleagues

Jason Papadopoulos - Block Lanczos code for quadratic sieve and multiprecision complex root finding code for polynomials.

Undergraduate Student Projects

Tomasz Lechowski - Contributed some NTL and Pari polynomial profiling code and researched algorithms for polynomials over finite fields. (Funded by the Nuffield Foundation)
Daniel Scott - Researched lazy and relaxed algorithms of Joris van der Hoeven. (Funded by Warwick University's Undergraduate Research Scholars Scheme)
David Howden - Wrote code for computing Bernoulli numbers mod many primes, including fast polynomial multiplication over Z/pZ specifically for the task. (Funded by Warwick University's Undergraduate Research Scholars Scheme)

Releases

The main functionality for version 1.0 is:

Polynomial arithmetic over Z,
Fast integer multiplication and factoring, including a highly optimised quadratic sieve.

Soon after 1.0, we hope to make a wrapper available in the free computer algebra system SAGE. An earlier release of FLINT is already available as a standard package in SAGE.

Get the development code

You will need a subversion client. The development repository is hosted by Sourceforge:

You can check out the repository with this command:

svn co http://flint.svn.sourceforge.net/svnroot/flint

Mailing list

Read the development mailing list archives.

References

http://citeseer.ist.psu.edu/bernstein98composing.html Bernstein - Composing power series, especially over ring with small characteristic.
cr.yp.to/bib/1998/kaltofen.pdf Kaltofen and Schoup - Probabilistic algorithm for factoring univariate polynomials over a finite field.
http://citeseer.ist.psu.edu/41327.html Victor Schoup - A discussion of various factoring algorithms over finite fields
http://citeseer.ist.psu.edu/403884.html Joris van der Hoeven - A description of Joris van der Hoeven's relaxed multiplication strategy and associated applications
http://citeseer.ist.psu.edu/680419.html Joris van der Hoeven - An improvement of relaxed multiplication techniques in rings with sufficiently many roots of unity (C mainly I would guess)
http://citeseer.ist.psu.edu/587176.html Joris van der Hoeven - A new relaxed product algorithm using a "middle product"
http://perso.ens-lyon.fr/damien.stehle/downloads/LLL25.pdf Damien Stehle - A very detailed paper describing the many tricks for speeding up LLL in floating point
http://scholar.lib.vt.edu/theses/available/etd-32298-93111/unrestricted/etd.pdf A thesis on the general number field sieve
http://cr.yp.to/papers.html#m3 Dan Bernstein - A detailed paper describing the algebra of every known multiprecision multiplication algorithm including many FFT tricks
http://cr.yp.to/papers.html#multapps Dan Bernstein - A detailed paper describing a very many algorithms for real, padic and multiprecision arithmetic
http://primes.utm.edu/prove/prove2_3.html A very useful page on primality proving
http://algo.inria.fr/seminars/sem00-01/schoenhage.html Arnold Schonhage - A paper describing some clever tricks for polynomial division
http://www.ams.org/mcom/0000-000-00/S0025-5718-07-02010-8/S0025-5718-07-02010-8.pdf Sam Wagstaff, Jason Gower - Very useful paper on SQUFOF and various heuristics associated with it
www.math.uiuc.edu/~landquis/quadsieve.pdf Eric Landquist - Excellent paper by an acquaintance of mine, on the quadratic sieve.

This site is hosted at sage.math.washington.edu thanks to William Stein