Fast Library for Number Theory

The Fast Library for Number Theory (FLINT) is a C library for number theory applications. It implements efficient versions of various ring arithmetics as well as derived functionality such as integer factorization using a quadratic sieve. The library is designed to be compiled with the GNU Multi-Precision Library (GMP) and is released under the GNU General Public License. It is developed by William Hart of the University of Kaiserslautern (formerly University of Warwick) and David Harvey of University of New South Wales (formerly Harvard University) to address the speed limitations of the PARI and NTL libraries.^[1]

FLINT along with a Cython wrapper for it is distributed with SageMath. The development of FLINT has led to significant contributions in the areas of integer factorization and polynomial arithmetic. For example as of May, 2007 on certain platforms FLINT factors integers in the quadratic sieve range faster than any other general implementation^[2], and as of February, 2008 it does arithmetic in ${\displaystyle \mathbb {Z} [x]}$ faster than any other package.^[3][4]

Core:

• Ring arithmetic (integers, rationals, algebraic, real, complex and p-adic numbers, finite fields, and number fields)
  • Exact real numbers (formerly the separate Calcium library)
  • Arbitrary-precision approximate real numbers with ball arithmetic (formerly the separate Arb library)^[5]
• Polynomials (univariate and multivariate), power series, and matrices building on top of ring arithmetics.

Based on core:

• Primality testing (APRCL, Miller-Rabin, BPSW, etc.)
• Integer factorization (trial factor, quadratic sieve, Pollard's rho, Lenstra ECM)
• Multivariate polynomial GCD and factorisation
• FFTs
• Multimodular reconstruction
• Special functions
• Exact and approximate linear algebra
• LLL
• Finite field embeddings
• ... and more.

FLINT maintains a webpage listing peer-reviewed papers, preprints, and other academic products making use of its functionality.^[5]

• FLINT 1.0.9: Fast Library for Number Theory by William Hart and David Harvey