FLINT: Fast Library for Number Theory

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

Download FLINT

25-Dec-09 FLINT 1.5.1 is released!!

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

06-Jul-09 FLINT 1.4.0 is released!!

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

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.

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.5.1 is available in the release tarball, or it can be downloaded here, flint-1.5.1.pdf.

Also Announcing....

FLINT 2! A new library which will eventually replace the FLINT 1.x series entirely

So far FLINT 2 contains:

• An entirely new ulong_extras module for arithmetic with unsigned integers right up to 64 bits
• The start of a new fmpz integer type (basically the F_mpz type introduced in FLINT 1.5), including a new threadsafe version
• The start of a new fmpz_poly module

Browse the development code with GitWeb:

or get a clone of the git repo with:

git clone http://selmer.warwick.ac.uk/flint2.git FLINT\-Lite

...and come and join the community of volunteers at our Google development group:

Current FLINT Development version (not stable)

NB: FLINT 1.5 will be the final stable version of FLINT in the 1.x series. All development effort from that point on will be devoted to the new FLINT 2 (see above).

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.

References to FLINT in the Literature and Online

• http://eprint.iacr.org/2009/203.pdf Practical Cryptanalysis of ISO/IEC 9796-2 and EMV Signatures - J-S Coron, D. Naccache, M. Tibouchi, R-P Weinmann (Univ. Luxembourg, Ecole Normale Superior)
• http://dx.doi.org/10.1016/j.tcs.2009.03.014 A cache-friendly truncated FFT - David Harvey (Univ. New York).
• http://cs.potsdam.edu/faculty/laddbc/Teaching/SeniorProjects/2009BartramCCSCNEPoster.pdf Poster about parallel factorisation - Ammon Bartram (Univ. Potsdam).
• http://www.informatik.uni-bremen.de/~malb/talks/20071110%20-%20Sage%20-%20Bristol.pdf Talk : Sage for Mathematical and Cryptographic Research - Martin Albrecht (Univ. Bremen) and William Stein (Univ. Washington).
• http://math.uci.edu/~ncalexan/research/stein-number-theory-sagetalk.pdf Talk : Sage for Number Theorists - William Stein (Univ. Washington).
• http://orms.mfo.de/extended_search?license=1 Oberwolfach References on Mathematical Software.
• http://wstein.org/talks/200906-horizon/June_11__What_is_on_the_Horizon.pdf Talk: Sage : What is on the Horizon - William Stein (Univ. Washington).
• http://www2.warwick.ac.uk/study/csde/urss/pastprojects/projects200708/richard_howell-peak_poster.pdf Poster about Factoring Algorithms over Finite Fields - Richard Howell-Peak (Univ. Warwick).
• http://modular.math.washington.edu/grants/sage-06/project_description.pdf Grant Proposal - William Stein (Univ. Washington).
• http://www.numbertheory.org/ntw/N1.html Number Theory Web - Number theory ftp sites/calculator programs/archives - Keith Matthews (Emer. Univ. Queensland).
• http://algo.inria.fr/seminars/sem08-09/kruppa-slides.pdf Talk : Fast Integer Multiplication with Schoenhage-Strassen's Algorithm - Alexander Kruppa (LORIA).
• http://en.wikipedia.org/wiki/Fast_Library_for_Number_Theory Wikipedia Article : Fast Library for Number Theory.
• http://www2.warwick.ac.uk/study/csde/urss/pastprojects/projects_06/david_howden.pdf Poster about Efficiently computing Bernoulli numbers using FLINT - David Howden (Univ. Warwick)
• http://www.williamstein.org/grants/frg07.pdf Grant Proposal - William Stein (Univ. Washington)
• http://www2.warwick.ac.uk/study/csde/urss/pastprojects/projects_06/daniel_scott_poster.pdf Poster about Implementing Middle Product in FLINT - Daniel Scott (Univ. Warwick)
• http://www2.warwick.ac.uk/study/csde/urss/pastprojects/projects200708/daniel_ellam_poster.ppt Poster about p-adic Arithmetic - Daniel Ellam (Univ. Warwick)
• http://mate.dm.uba.ar/~pdenapo/mathsoft.html Programas utiles para Mathematica - Pablo De Napoli (Univ. Buenos Aires)

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,

Version 1.3.x added:

• Full factor command for unsigned longs, including call to quadratic sieve for larger integers
• Fast 2nd, 3rd and 5th root checking for unsigned longs
• An implementation of Hart's One Line Factor algorithm for unsigned longs

Version 1.4.x added:

• Faster polynomial division over Z/pZ
• Much faster polynomial GCD over Z/pZ
• Asymptotically faster polynomial resultant over Z/pZ
• Optimised polynomial remainder functions over Z/pZ

A wrapper is available in the free computer algebra system SAGE. As of version 3.0.4 of SAGE, FLINT is used as the default package for arithmetic in Z[x] in the Sage package. More recently Sage now uses FLINT for the default library for polynomial arithmetic over Z/nZ. Note that FLINT speeds up basic polynomial arithmetic over Z/nZ by making use of zn_poly.

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