FLINT: Fast Library for Number Theory

FLINT is a C library for doing number theory, maintained by William Hart.

Download FLINT

09-Jun-09 FLINT 1.3.0 is released!!

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

18-Apr-09 FLINT 1.2.5 is released!!

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

Warning: In FLINT 1.2.5 the function z_factor may fail to factor unsigned longs very rarely.

1-Mar-09 FLINT 1.1.3 is released!!

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

25-Dec-08 FLINT 1.0.21 is released!!

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

FLINT Documentation

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

Development version (not stable)

09-Jun-09 FLINT 1.4-devel

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

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

Contributors

International Colleagues

• David Harvey - Fast Fourier Transform code, zn_poly for polynomial arithmetic over Z/nZ, mpz_poly, profiling and graphing code and many other parts of the FLINT library
• Jason Papadopoulos - Block Lanczos code for quadratic sieve and multiprecision complex root finding code for polynomials.
• Gonzalo Tornaria - Theta function module, Montgomery multiplication and significant contributions to the Z[x] modular multiplication code.
• Burcin Erocal - wrote the primary FLINT wrapper in the SAGE system (Robert Bradshaw also wrote a preliminary version of this).
• Andy Novocin - Polynomial composition, alias testing, documentation
• Tom Boothby - Improved factoring of unsigned longs, detection of perfect powers

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)
• Daniel Ellam - Helped design a module for p-adic arithmetic for FLINT. (Funded by Warwick University's Undergraduate Research Scholars Scheme)
• Richard Howell-Peak - Wrote polynomial factorisation and irreducibility testing code for polynomials over Z/pZ. (Funded by Warwick University's Undergraduate Research Scholars Scheme)
• Peter Shrimpton - Wrote code for a basic prime sieve, Pocklington-Lehmer, Lucas, Fibonacci, BSPW and "n-1" primality tests and a Weiferich prime search. (Funded by the Nuffield Foundation)

Additional Contributors

• Bugs have been reported by Michael Abshoff (numerous), Craig Citro, Timothy Abbot, Carl Witty, Gonzalo Tornaria, Jaap Spies, Kiran Kedlaya, William Stein, Kate Minola, Didier Deshommes and possibly others.
• Patches have been contributed by Andy Novocin, Gonzalo Tornaria and Didier Deshommes.
• In addition Michael Abshoff, William Stein and Robert Bradshaw have contributed to the build system of FLINT.
• Michael Abshoff deserves special recognition for his help in resolving a number of difficult build issues which came to light as FLINT has been used in SAGE and for bringing numerous bugs to the attention of the FLINT maintainers. Michael has regularly checked FLINT for memory leaks and corruption, which has directly led to numerous issues being identified early! He has also helped with setting up various pieces of infrastructure such as the FLINT trac server.

Releases

The main functionality for version 1.0.x is:

• Polynomial arithmetic over Z,
• Polynomial arithmetic over Z/pZ for a word sized prime p,
• Fast integer multiplication and factoring, including a highly optimised quadratic sieve.

Version 1.1.x added:

• Polynomial GCD, resultant, derivative, composition, evaluation, content over Z,
• Polynomial GCD, resultant, derivative, middle product and factoring over Z/pZ for a word sized prime p,
• Montgomery format and multimodular arithmetic over Z,
• Theta functions,
• Primality testing for word sized primes,
• A tiny quadratic sieve.

Version 1.2.x added:

• Switch to zn_poly for basic arithmetic in Z/nZ[x],
• Polynomial pseudo remainder and signature over Z,
• Cube root, further primality tests and squarefree functions for word sized primes,

Get the development code

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

• Main project page
• Browse SVN repository

You can check out the repository with this command:

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

Reporting Bugs

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://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.57.6285 Joris van der Hoeven - Relaxed Multiplication Using the Middle Product
• http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.5.4472 Joris van der Hoeven - New algorithms for relaxed multiplication
• http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.20.897 Joris van der Hoeven - Relax but don't be too lazy
• 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.
• https://computing.llnl.gov/tutorials/openMP/ Tutorial on using OpenMP.
• http://www.springerlink.com/content/g151433l21m47622/ Old article on doing exact rational arithmetic with "finite segment" p-adic arithmetic. Better for division than multimodular arithmetic.
• http://islab.oregonstate.edu/papers/r09padic.pdf Another paper on Hensel codes and finite segment p-adic arithemtic, but not much different to the above.
• http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=6634 A further paper on Hensel codes and finite segment p-adic arithmetic, correcting numerous errors in previous work on the subject.
• http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1674895 Yet another very old paper on Hensel codes, this time with applications to matrix algebra over Q.
• http://www.azillionmonkeys.com/qed/sqroot.html Paul Hsieh - Excellent description of various algorithms for computing floating point and integer square roots efficiently.
• http://www.infsec.cs.uni-sb.de/~backes/papers/Masterthesis-math.pdf Michael Backes - Masters thesis on univariate polynomial factorisation.
• http://www.springerlink.com/content/tv56418752641456/ Harald Niederreiter - Algorithm for factoring polynomials over finite fields.
• http://www.jstor.org/sici?sici=0025-5718(199501)64%3A209%3C347%3AOANFAF%3E2.0.CO%3B2-P Harald Niederreiter, Rainer Gottfert - Algorithm for factoring polynomials over finite fields.
• http://www.ams.org/leavingmsn?url=http://dx.doi.org/10.1016/j.jsc.2006.02.007 Julio Genovese - Improvement of the Berlekamp/Niederriter algorithms for factoring polynomials over finite fields.
• http://www.shoup.net/papers/frobenius.pdf Victor Shoup, Joachim von zur Gathen - Frobenius and trace map algorithm for factoring polynomials over finite fields.
• http://www.jstor.org/stable/2005583?seq=1 Brillhart, Lehmer, Selfridge - Numerous primality proving algorithms.
• http://citeseer.ist.psu.edu/old/gao97tests.html Gao, Panario - Numerous algorithms for testing irreducibility of polynomials.
• http://citeseer.ist.psu.edu/old/panario00analysis.html Panario, Pittel, Richmond, Viola - Analysis of Rabin's irreducibility test for polynomials.
• http://www.ingvet.kau.se/~igor/Statji/statja(2005)1.pdf Gashkov, Gashkov - Improvements for Rabin's polynomial irreducibility test.
• http://www.cs.caltech.edu/~umans/papers/U07.pdf Umans - Fast modular composition (f(g(x)) modulo h(x)) over Z/pZ and asymptotically fast polynomial factorisation.
• http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.46.1941 Yap, Thul - Half GCD algorithm for both integers and polynomials.
• http://arxiv.org/abs/0712.4046 David Harvey - A paper detailing two new algorithms for Kronecker Segmentation, called KS2 and KS4.
• http://arxiv.org/PS_cache/cs/pdf/0206/0206032v1.pdf Bernard Parisse - Details a proven bound for the heuristic gcd algorithm for polynomials (univariate and multivariate).