FLINT is a C library for doing number theory, maintained by William Hart. FLINT is licensed GPL v2+.
The main authors of FLINT are *William Hart, **Sebastian Pancratz, Andy Novocin, ***Fredrik Johansson
and David Harvey (past author).
Supported by: * EPSRC Grant EP/G004870/1, ** ERC Grant 204083, *** Austrian Science Foundation (FWF) grant Y464-N18
News
There is to be a Sage Days on the topic of Number Theory and FLINT at Warwick University from 17-22nd Dec.
Anyone interested in learning to use Sage or FLINT is welcome to register to attend. Details can be found
here.
Andy Novocin - LLL, polynomial factorisation over ZZ, polynomial composition
Sebastian Pancratz - polynomial arithmetic over ZZ and QQ
Fredrik Johansson - linear algebra, arithmetic functions
Jan Tuitman - helped with the p-adic interface
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 and Martin Albrecht and others have also contributed to it.)
Tom Boothby - Improved factoring of unsigned longs, detection of perfect powers
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)
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, Serge Torres and possibly others.
Patches have been contributed by 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 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.
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
Version 1.5.x added:
Multimodular reduction and CRT and powering for F_mpz's
Composition and evaluation for polys over Z/nZ
"Trillion Triangle's" large theta product multiplication code
Version 1.6.x added:
Factoring polynomials over Z
Restartable Hensel lifting
Optimised LLL (especially for knapsack lattices)
Matrices over Z
Polynomials over Z/nZ for large n
Many other features
Version 2.0.x contains:
A ulong_extras module for arithmetic with unsigned integers right up to 64 bits
An fmpz module for multiprecision integers
An fmpz_poly module for polynomials over fmpz integers.
An fmpz_vec module for basic vector operations using the new fmpz integer type.
An fmpz_mat module for matrix operations using the new fmpz integer type.
An fmpq_poly module for polynomials over the rationals.
An mpfr_vec module for basic vector operations over floating point reals.
An mpfr_mat module for matrices over floating point reals.
An nmod_vec module for basic vector operations over Z/nZ for small n.
An nmod_mat module for matrices over Z/nZ for small n.
An nmod_poly module for univariate polynomials over Z/nZ for small n.
Version 2.1.x added:
An arith module for fast computation of arithmetic functions
Fast power series transcendental functions in fmpq_poly
Fast square root, inverse square root and power series transcendental functions in nmod_poly
Computation of right null spaces and multimodular determinant in fmpz_mat
Faster determinants, gaussian elimination and matrix inversion in nmod_mat
Many new fmpz functions including binomial coefficients and CRT
Version 2.2.x added:
An fmpq module for multiprecision rationals
An fmpq_mat module for matrices over Q
An fmpz_poly_mat module for matrices over Z[x]
An fmpz_poly_q module for rational functions (quotients of integer polys)
A padic module for padic numbers
Inlined functions in fmpz module for improved performance
Dixon's padic function, RREF and CRT functions for fmpz_mat
Sped up matrix multiplication in fmpz_mat
xgcd for nmod_poly module
modular gcd for fmpz_poly module
xgcd for fmpz_poly module
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.
Reporting Bugs
Bugs can be reported to hart_wb {at_thingy} yahoo dot com or preferably at our mailing list.
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