FLINT: Fast Library for Number Theory
FLINT is a C library for doing number theory, maintained by William Hart. FLINT is licensed GPL v2+.
FLINT developers Workshop 4-12 May, announcement
There will be a FLINT Workshop at Warwick University from May 4-12. We have funds to support visiting researchers of "established standing", i.e. have a lectureship or equivalent or work in relevant industry which has an interest in the research.
We will be working on the following topics
- LLL in flint
- polynomial factorisation in flint
- linear algebra in flint
- ball arithmetic in arb (a new library by Fredrik Johansson based on flint)
- finite fields in flint
- C++ wrapper for flint
- algebraic number theory in flint
- integer factorisation in flint
- using flint to compute symmetric Hilbert modular forms
- Sage/flint interface, esp. Sage trac #14304
- Flint/Singular interface
If you would like to attend, please register at http://www2.warwick.ac.uk/fac/sci/maths/research/events/2012-2013/nonsymp/flint/ whether we are able to fund you or not.
For a list of changes, see the NEWS file.
FLINT 2.x series:
FLINT 1.x series:
You can get a clone of the git development repo with:
git clone git://github.com/wbhart/flint2.git flint2
If you want to browse the repository online, it can be accessed here:
The current development branch within the repository is "trunk".
...and come and join the growing community of volunteers at our Google development group:
flint-devel Google Group
FLINT provides types and functions for computing over various base rings. FLINT uses many new algorithms (see bibliography) and is sometimes orders of magnitude faster than other available software (some examples are given on the benchmarks page).
FLINT is written in ANSI C and runs on many platforms, but is currently mostly optimised for x86 and x86-64 architectures. It is designed to be threadsafe. FLINT depends on the MPIR (GMP) and MPFR libraries.
The following is a partial list of features in FLINT as of version 2.3:
- Basic arithmetic
- Arbitrary-precision integers and rationals, particularly fast for small coefficients
- Code for efficient representation and manipulation of vectors of numbers
- A fast Schönhage-Strassen FFT for large multiplications
- Functions for word-size integers (up to 32 or 64 bits)
- Division and remainder using precomputed inverse
- Modular arithmetic
- Factorisation and primality testing
- A quadratic sieve for factoring numbers up to two words (64 or 128 bits)
- Number-theoretic functions (GCD, Jacobi symbol, Euler phi, etc.)
- p-adic numbers (experimental)
- Arithmetic operations
- Exponential, logarithm, Teichmuller lift
- Dense univariate polynomials over Z, Q, Z/nZ for word-size n and Z/nZ for arbitrary-precision n; rational functions over Q
- Basic arithmetic, powering, evaluation, composition
- Most operations take advantage of asymptotically fast polynomial multiplication (Kronecker substitution, Schönhage-Strassen)
- Euclidean division, GCD, extended GCD, resultants
- Power series operations (multiplication, division, composition, reversion, transcendental functions)
- Factorisation over Z/nZ for word-size n, factorisation over Z
- Interpolation, Chinese remaindering, bit packing
- Restartable Hensel lifting
- Asymptotically fast GCD; modular and heuristic GCD algorithms over Z
- Matrices (experimental)
- Dense matrices over Z, Q, Z/nZ for word-size n, Z[x], and (Z/nZ)[x] for word-size n
- Multiplication, determinant, rank, LU decomposition, reduced row echelon form, nonsingular solving, null space
- Asymptotically fast linear algebra over Z/nZ (Strassen-Winograd multiplication, block recursive echelon form)
- Fast solving over Z and Q using p-adic lifting; multimodular algorithms for multiplication and determinants
- Arithmetic and special functions (experimental)
- Divisor sums, Moebius mu, Euler phi, etc.
- Number of partitions, Bernoulli numbers, Stirling numbers, etc.
- Bernoulli polynomials, cyclotomic polynomials, etc.
The following features are currently only available in the FLINT 1.x series.
They will be added to the FLINT 2.x series in the future:
- Lattice reduction (optimised LLL, especially for knapsack lattices); faster factorisation over Z
The following program computes and prints (2 + 3x + 5x2 + 7x3 + 11x4)2.
A few more example programs can be found in the examples directory.
fmpz_poly_t f, g;
for (i = 0; i < 5; i++)
fmpz_poly_set_coeff_ui(f, i, n_nth_prime(i + 1));
fmpz_poly_mul(g, f, f);
- William Hart - integer and polynomial arithmetic, factorisation and primality testing, general infrastructure (supported by EPSRC Grant EP/G004870/1)
- Sebastian Pancratz - polynomial arithmetic over Z, Z/nZ and Q, p-adic arithmetic (supported by ERC Grant 204083)
- Andy Novocin - LLL, polynomial factorisation over Z, polynomial composition
- Fredrik Johansson - matrices, polynomial and power series arithmetic, special functions (supported by Austrian Science Fund FWF Grant Y464-N18)
- David Harvey (past author) - 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
- Jan Tuitman - helped with the p-adic interface
- 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 and Martin Albrecht and others have also contributed to it.)
- Tom Boothby - Improved factoring of unsigned longs, detection of perfect powers
- Andres Goens - Fq module and polynomials over Fq
- Lina Kulakova - factorisation for polynomials over F_p for large p
- Thomas DuBuisson - logical ops for fmpz module, patches to the build system
- Jean-Pierre Flori - many build system patches and Sage integration
- Frithjof Schulze - some fmpz functions and various patches
- Curtis Bright - numerous patches including 32 bit support
Undergraduate Student Projects
- Daniel Woodhouse - Contributed an implementation of multivariate multiplication over Z/nZ and used this
to implement a fast "saturation" algorithm for Laurent polynomials. (Funded by Alessio Corti and Tom Coates at Imperial College)
- 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)
- Further patches and bug reports have been made by Michael Abshoff, Didier
Deshommes, Craig Citro, Timothy Abbot, Carl Witty, Gonzalo Tornaria, Jaap Spies, Kiran
Kedlaya, William Stein, Kate Minola, Didier Deshommes, Robert Bradshaw, Serge Torres, Dan
Grayson, Martin Lee, Bob Smith, Antony Vennard, Frederic Chyzak, Julien
Puydt and many others.
- 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 was incorporated into SAGE and for bringing numerous bugs to the attention of the FLINT maintainers.
Michael regularly checked FLINT for memory leaks and corruption, which directly led to numerous issues being identified
early! He also helped with setting up various pieces of infrastructure for the FLINT project.
- Numerous people have contributed to wrapping FLINT in Sage and debugging,
including Mike Hansen, Jean-Pierre Flori, Burcin Erocal, Robert Bradshaw,
Martin Albrecht, Sebastian Pancratz, Fredrik Johansson.
Links and References
Software using FLINT
- Sage uses FLINT as the default package for polynomial arithmetic over Z, Q and Z/nZ for small n.
- Work is currently in progress to use FLINT in Singular.
- Scarab library - an implementation of fully homomorphic encryption using FLINT.
References to FLINT in the Literature and Online
Practical divide-and-conquer algorithms for polynomial arithmetic
- W. Hart (Univ. Warwick) and A. Novocin (Univ. Waterloo)
Efficient implementation of the Hardy-Ramanujan-Rademacher formula - F. Johansson (RISC, Linz)
A fast algorithm for reversion of power series - F. Johansson (RISC, Linz)
An introduction to FLINT (pp. 88-91) - W. Hart (Univ. Warwick)
FLINT 2 benchmarking - F. Johansson (RISC, Linz)
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)
A cache-friendly truncated FFT - David Harvey (Univ. New York).
Poster about parallel factorisation - Ammon Bartram (Univ. Potsdam).
Talk : Sage for Mathematical and Cryptographic Research - Martin Albrecht (Univ. Bremen) and William Stein (Univ. Washington).
Talk : Sage for Number Theorists - William Stein (Univ. Washington).
Oberwolfach References on Mathematical Software.
Talk: Sage : What is on the Horizon - William Stein (Univ. Washington).
Poster about Factoring Algorithms over Finite Fields - Richard Howell-Peak (Univ. Warwick).
Grant Proposal - William Stein (Univ. Washington).
Number Theory Web - Number theory ftp sites/calculator programs/archives - Keith Matthews (Emer. Univ. Queensland).
Talk : Fast Integer Multiplication with Schoenhage-Strassen's Algorithm - Alexander Kruppa (LORIA).
Wikipedia Article : Fast Library for Number Theory.
Poster about Efficiently computing Bernoulli numbers using FLINT - David Howden (Univ. Warwick)
Grant Proposal - William Stein (Univ. Washington)
Poster about Implementing Middle Product in FLINT - Daniel Scott (Univ. Warwick)
Poster about p-adic Arithmetic - Daniel Ellam (Univ. Warwick)
Programas utiles para Mathematica - Pablo De Napoli (Univ. Buenos Aires)
Implementation of new polynomial factoring algorithm - van Hoeij, Novocin, Hart.
Methods and implementations for integer factorization (slides) - D. Jacobsen.
Using the FLINT FFT for (string) pattern matching - B. Smithers (?).
The zn_poly library - D. Harvey (CIMS, New York)
Mathematics, Algorithms and Implementation
Some more references can be found in the FLINT documentation.
- Bernstein - Composing power series, especially over ring with small characteristic
- Kaltofen and Shoup - Probabilistic algorithm for factoring univariate polynomials over a finite field
- Victor Shoup - A discussion of various factoring algorithms over finite fields
- Joris van der Hoeven - Relaxed Multiplication Using the Middle Product
- Joris van der Hoeven - New algorithms for relaxed multiplication
- Joris van der Hoeven - Relax but don't be too lazy
- Damien Stehle - A very detailed paper describing the many tricks for speeding up LLL in floating point
- A thesis on the general number field sieve
- Dan Bernstein - A detailed paper describing the algebra of every known multiprecision multiplication algorithm including many FFT tricks
- Dan Bernstein - A detailed paper describing a very many algorithms for real, padic and multiprecision arithmetic
- A very useful page on primality proving
- Arnold Schonhage - A paper describing some clever tricks for polynomial division
- Sam Wagstaff, Jason Gower - Very useful paper on SQUFOF and various heuristics associated with it
- Eric Landquist - Excellent paper by an acquaintance of mine, on the quadratic sieve
- Tutorial on using OpenMP
- Old article on doing exact rational arithmetic with "finite segment" p-adic arithmetic. Better for division than multimodular arithmetic.
- Another paper on Hensel codes and finite segment p-adic arithmetic, but not much different to the above.
- A further paper on Hensel codes and finite segment p-adic arithmetic, correcting numerous errors in previous work on the subject.
- Yet another very old paper on Hensel codes, this time with applications to matrix algebra over Q.
- Paul Hsieh - Excellent description of various algorithms for computing floating point and integer square roots efficiently.
- Michael Backes - Masters thesis on univariate polynomial factorisation.
- Harald Niederreiter - Algorithm for factoring polynomials over finite fields.
- Harald Niederreiter, Rainer Gottfert - Algorithm for factoring polynomials over finite fields.
- Julio Genovese - Improvement of the Berlekamp/Niederriter algorithms for factoring polynomials over finite fields.
- Victor Shoup, Joachim von zur Gathen - Frobenius and trace map algorithm for factoring polynomials over finite fields.
- Brillhart, Lehmer, Selfridge - Numerous primality proving algorithms.
- Gao, Panario - Numerous algorithms for testing irreducibility of polynomials.
- Panario, Pittel, Richmond, Viola - Analysis of Rabin's irreducibility test for polynomials.
- Gashkov, Gashkov - Improvements for Rabin's polynomial irreducibility test.
- Umans - Fast modular composition (f(g(x)) modulo h(x)) over Z/pZ and asymptotically fast polynomial factorisation.
- Yap, Thul - Half GCD algorithm for both integers and polynomials.
- David Harvey - A paper detailing two new algorithms for Kronecker Segmentation, called KS2 and KS4.
- Bernard Parisse - Details a proven bound for the heuristic gcd algorithm for polynomials (univariate and multivariate).
- van Hoeij, Novocin - Improvements in factoring polynomials over Z.
- van Hoeij, Novocin, Hart - Implementation of new polynomial factoring algorithm.
- Novocin, Stehle, Villard - Quasi-linear LLL.
This site is hosted at sage.math.washington.edu thanks to William Stein.