FLINT: Fast Library for Number Theory#

FLINT is a C library for number theory and computer algebra: arithmetic with integers, rationals, polynomials, matrices, finite fields, p-adic numbers, and real and complex numbers with rigorous error bounds.

The documentation has four parts:

• The User guide explains how to build and use FLINT and the conventions shared by all modules: types, memory management, aliasing, threads, ball arithmetic and exact numbers.
• The modules below document every public function, module by module, grouped by subject. Each module page lists all functions with their full prototypes and a short description; function pages and guides give the details, usually with a short complete program.
• Algorithms describes the methods behind the functions, with proofs, complexity and references, starting from the generic algorithms and leading to the specialised implementations.
• Examples and tutorials develop complete programs step by step.

Every example program in the documentation is compiled and run by make checkdoc, and its output is compared with the output shown.

Start here#

Modules#

Foundations

flint.hWord types, version macros, memory allocation, caches and cleanup, random states, formatted I/O, exceptions and sorting.profiler.hTimers for quick benchmarks, cycle counters and memory usage reports.thread_pool.hThe pool of worker threads that all parallel code in FLINT draws from.thread_support.hThread limits, parallel loops, parallel binary splitting and lock-free shared caches.machine_vectors.hShort SIMD vectors of doubles, floats and words, exact modular arithmetic in floating point, and FLINT's own sgemm and dgemm.longlong.hMacros for double-word and multi-word arithmetic on limbs, bit counting and division with precomputed inverses.perm.hPermutations of {0, ..., n-1} stored as arrays of slong: composition, inversion, parity, random permutations and enumeration.

Word-size integers

ulong_extras.hArithmetic and number theory for single-word unsigned integers.long_extras.hFunctions for signed words: digit counts, overflow-checked arithmetic, sign of a 2x2 determinant, random values and the Kronecker symbol.

Integers

fmpz.hArbitrary-precision integers with an inline representation of small values: arithmetic, division with all rounding conventions, GCDs, roots, modular arithmetic, Chinese remaindering, bit operations, primality testing and combinatorial functions.fmpz_vec.hVectors of integers as plain arrays of fmpz: memory management, norms, arithmetic, scalar multiplication and division, content, products, Chinese remaindering and dot products.fmpz_extras.hInline fast paths for fmpz arithmetic on small values, and helpers for exponents, limb access and memory accounting.fmpz_factor.hFactorisation of integers into proven primes, and the factoring methods behind it: trial division, Pollard rho, p + 1 and the elliptic curve method.mpn_extras.hArithmetic on natural numbers stored as arrays of limbs, extending and replacing GMP's mpn layer.crt_helpers.hInline fixed-length carry chains and the Chinese remaindering kernels shared by fft_small and the multimodular code.radix.hMultiprecision arithmetic in a general radix such as 10^{19} or a power of a prime, with conversion to and from binary.qsieve.hThe self-initialising multiple polynomial quadratic sieve for factoring integers of 40 to 90 digits.aprcl.hThe APRCL primality test with Jacobi sums, and arithmetic in cyclotomic rings modulo n.ecpp.hElliptic curve primality proving with verifiable certificates.

Rational numbers

fmpq.hRational numbers as fractions of multiprecision integers in canonical form, with arithmetic, rational reconstruction, continued fractions and enumeration of the rationals.fmpq_vec.hVectors of rational numbers stored as arrays of fmpq.

Integers mod n

nmod.hArithmetic in \mathbb{Z}/n\mathbb{Z} for a word-size modulus n, with Montgomery arithmetic, square roots and discrete logarithms.nmod_vec.hVectors over \mathbb{Z}/n\mathbb{Z} for word-size n, stored as plain arrays of ulong.fmpz_mod.hArithmetic in \mathbb{Z}/n\mathbb{Z} for a modulus n of any size, with residues stored as fmpz integers, and discrete logarithms modulo primes.fmpz_mod_vec.hVectors of residues modulo n stored as fmpz arrays, with elementwise arithmetic, scalar multiplication and dot products with a single reduction.mpn_mod.hArithmetic in \mathbb{Z}/n\mathbb{Z} for moduli of 2 to 16 limbs, with residues stored as fixed-length limb arrays, as a generic ring with fast vector, polynomial and matrix methods.

Number theory

arith.hNumber-theoretic and combinatorial sequences — Bernoulli, Euler, Stirling and Bell numbers, partitions, sums of squares, Ramanujan's tau function, divisors and Landau's function.bernoulli.hExact Bernoulli numbers — isolated values by the zeta function and Harvey's multimodular algorithm, ranges by a reverse zeta iterator, residues modulo primes, and a global cache.partitions.hThe partition function p(n) for huge n by the Hardy–Ramanujan–Rademacher formula, with rigorous error bounds.dirichlet.hDirichlet characters modulo a word-size integer, in the Conrey numbering, with exact values as exponents of roots of unity.dlog.hDiscrete logarithms modulo word-size prime powers with precomputed tables chosen for an expected number of queries, and vectors of logarithms of consecutive integers.qfb.hPositive definite binary quadratic forms — reduction, enumeration of the reduced forms of a discriminant, NUCOMP composition, powering, and the order and exponent of the form class group.

Univariate polynomials

fmpz_poly.hDense univariate polynomials over the integers, from basic arithmetic to fast multiplication, division, GCDs, resultants, evaluation, composition, power series, real root isolation and Hensel lifting.fmpz_poly_factor.hFactorisation of polynomials over the integers into irreducible factors, by squarefree factorisation, Hensel lifting and the Zassenhaus and van Hoeij recombination algorithms.fmpq_poly.hDense univariate polynomials over \mathbb{Q}, stored as an integer polynomial with a common denominator, with arithmetic, division, GCDs, power series and transcendental functions, composition, reversion and interpolation.fmpz_poly_q.hRational functions in \mathbb{Q}(x), stored as canonical quotients of integer polynomials.nmod_poly.hDense univariate polynomials over \mathbb{Z}/n\mathbb{Z} for a word-size modulus n, from basic arithmetic to fast multiplication, division, GCDs, evaluation, interpolation, composition and power series.nmod_poly_factor.hFactorisation, irreducibility and squarefreeness testing, and root finding for polynomials over \mathbb{Z}/n\mathbb{Z} with word-size modulus.n_poly.hLightweight dense and sparse polynomial containers over Z/pZ and F_q with word-size coefficients, used internally by the multivariate polynomial code.fmpz_mod_poly.hDense univariate polynomials over \mathbb{Z}/n\mathbb{Z} for a modulus of any size, with fast multiplication, division, GCDs, modular composition, evaluation and power series.fmpz_mod_poly_factor.hFactorisation, irreducibility and squarefreeness testing, and root finding for polynomials over \mathbb{Z}/n\mathbb{Z} with multiword modulus.

Multivariate polynomials

mpoly.hInfrastructure shared by all sparse multivariate polynomial modules: monomial orderings, packed exponent vectors, monomial arithmetic, heaps, and helpers for GCD and factorisation.fmpz_mpoly.hSparse multivariate polynomials over the integers, with heap, array and dense multiplication and division, square roots, GCDs, resultants and Gröbner bases.fmpz_mpoly_factor.hFactorisation of multivariate polynomials over the integers into content, squarefree and irreducible factors, with the multimodular GCD, Hensel lifting and dense bivariate machinery behind it.fmpz_mpoly_q.hMultivariate rational functions over the rationals, as reduced fractions of integer polynomials, optionally with factored denominators.fmpq_mpoly.hSparse multivariate polynomials over the rational numbers, stored as a rational content times a primitive integer polynomial.fmpq_mpoly_factor.hFactorisation of multivariate polynomials over the rational numbers, by reduction to the integers.nmod_mpoly.hSparse multivariate polynomials over \mathbb{Z}/n\mathbb{Z} for a word-size modulus n, with heap, array and Kronecker multiplication, heap division, GCDs with extension-field fallbacks for small fields, square roots and resultants.nmod_mpoly_factor.hFactorisation of multivariate polynomials over \mathbb{F}_p for a word-size prime p, into content, squarefree, separable and irreducible factors, with extension-field methods for small fields.fmpz_mod_mpoly.hSparse multivariate polynomials over \mathbb{Z}/n\mathbb{Z} for a modulus n of any size, with heap arithmetic, GCDs, square roots, resultants and naive Gröbner bases.fmpz_mod_mpoly_factor.hFactorisation of multivariate polynomials over \mathbb{F}_p for a prime p of any size, and the GCD and lifting machinery behind fmpz_mod_mpoly.fmpz_mod_mpoly_q.hMultivariate rational functions over a prime field \mathbb{F}_p, as reduced fractions of fmpz_mod_mpoly polynomials with monic denominators.fq_nmod_mpoly.hSparse multivariate polynomials over finite fields \mathbb{F}_q of word-size characteristic, with heap arithmetic, GCDs that fall back to extension fields for small q, square roots and resultants.fq_nmod_mpoly_factor.hFactorisation of multivariate polynomials over finite fields \mathbb{F}_q of word-size characteristic, with extension-field methods for small fields.fq_zech_mpoly.hSparse multivariate polynomials over small finite fields with coefficients in Zech logarithm representation; a partial port of fq_nmod_mpoly used mainly by the factoring code of nmod_mpoly.fq_zech_mpoly_factor.hFactorisation of multivariate polynomials over small finite fields in Zech logarithm representation, and the bivariate and lifting machinery used by the medprime factoring algorithms of nmod_mpoly.

Matrices

fmpz_mat.hDense matrices over the integers, with multiplication, determinants, exact solving over \mathbb{Q}, echelon forms, Hermite and Smith normal forms, characteristic polynomials and lattice reduction.fmpz_lll.hLLL reduction of integer lattices given by a basis or a Gram matrix, with floating-point Gram–Schmidt data (L² algorithm), certified reducedness tests and removals of long vectors.fmpq_mat.hDense matrices over the rational numbers, with conversions to integer matrices, multiplication, determinants, linear system solving, echelon forms and characteristic polynomials computed over the integers.nmod_mat.hDense matrices over \mathbb{Z}/n\mathbb{Z} for word-size n, with fast multiplication, LU decomposition, linear solving, echelon forms and characteristic polynomials.fmpz_mod_mat.hDense matrices over \mathbb{Z}/n\mathbb{Z} for a modulus of any size, with entries stored as fmpz residues, multiplication by exact integer products, and Gaussian elimination through the generic matrix algorithms.fmpz_poly_mat.hDense matrices of polynomials over the integers, with multiplication by Kronecker substitution, determinants by fraction-free elimination or interpolation, and exact solving with polynomial denominators.nmod_poly_mat.hDense matrices of polynomials over \mathbb{Z}/n\mathbb{Z} for word-size n, with multiplication by Kronecker substitution, evaluation and interpolation or the small-prime FFT, determinants, and exact solving by fraction-free elimination.bool_mat.hDense matrices over the Boolean semiring, with products, powers, transitive closure and graph algorithms on adjacency matrices.

Finite fields

fq_default.hFinite fields \mathbb{F}_q of any order, with the representation (Zech logarithms, word-size or multiprecision characteristic, prime field) chosen automatically.fq_default_mat.hDense matrices over any finite field \mathbb{F}_q, in the representation chosen by fq_default.fq_default_poly.hDense univariate polynomials over any finite field \mathbb{F}_q, in the representation chosen by fq_default.fq_default_poly_factor.hFactorisation, irreducibility testing and root finding for polynomials over any finite field \mathbb{F}_q, in the representation chosen by fq_default.fq.hFinite fields \mathbb{F}_{p^d} of arbitrary characteristic, with elements stored as polynomials over \mathbb{Z}/p\mathbb{Z} with multiprecision coefficients.fq_vec.hVectors over finite fields \mathbb{F}_q of arbitrary characteristic, stored as arrays of fq_struct.fq_mat.hDense matrices over finite fields \mathbb{F}_q of arbitrary characteristic, with Kronecker substitution multiplication and linear algebra through the generic gr_mat algorithms.fq_poly.hDense univariate polynomials over finite fields \mathbb{F}_q of arbitrary characteristic, with Kronecker substitution multiplication and generic fast division, GCD, composition and power series algorithms.fq_poly_factor.hFactorisation, irreducibility and squarefreeness testing and root finding for polynomials over finite fields \mathbb{F}_q of arbitrary characteristic.fq_embed.hEmbeddings of a finite field \mathbb{F}_{p^m} into \mathbb{F}_{p^n}, m \mid n, given by different defining polynomials, as matrices over \mathbb{F}_p, with projections by the trace.fq_nmod.hFinite fields \mathbb{F}_{p^d} of word-size characteristic, with elements stored as polynomials over \mathbb{Z}/p\mathbb{Z} (nmod_poly).fq_nmod_vec.hVectors over finite fields \mathbb{F}_q in the word-size characteristic.fq_nmod_mat.hDense matrices over finite fields \mathbb{F}_q in the word-size characteristic.fq_nmod_poly.hDense univariate polynomials over finite fields \mathbb{F}_q in the word-size characteristic.fq_nmod_poly_factor.hFactorisation of polynomials over finite fields \mathbb{F}_q in the word-size characteristic.fq_nmod_embed.hEmbeddings between finite fields in the word-size characteristic.fq_zech.hSmall finite fields \mathbb{F}_q, q < 2^{64}, with elements stored as discrete logarithms (Zech logarithm representation).fq_zech_vec.hVectors over finite fields \mathbb{F}_q in the Zech logarithm representation.fq_zech_mat.hDense matrices over finite fields \mathbb{F}_q in the Zech logarithm representation.fq_zech_poly.hDense univariate polynomials over finite fields \mathbb{F}_q in the Zech logarithm representation.fq_zech_poly_factor.hFactorisation of polynomials over finite fields \mathbb{F}_q in the Zech logarithm representation.fq_zech_embed.hEmbeddings between finite fields in the Zech logarithm representation.

p-adic numbers

padic.hElements of the p-adic field \mathbf{Q}_p as p^v u reduced modulo p^N, with inversion, square roots, exponential, logarithm and Teichmüller lifts.padic_poly.hPolynomials over the p-adic numbers, stored as p^v f(x) with f \in \mathbb{Z}[x] reduced modulo p^{N - v}.padic_mat.hMatrices over the p-adic numbers, stored as p^v M with an integer matrix M reduced modulo p^{N - v}.qadic.hUnramified extensions \mathbf{Q}_q = \mathbf{Q}_p[X]/(f) of the p-adic numbers, with inversion, square roots, exponential, logarithm, the Frobenius automorphism, Teichmüller lifts, norm and trace.padic_radix.hp-adic numbers for word-size p in a radix p^e representation, with tracked error terms, absolute and relative precision, and the generic ring interface.

Algebraic numbers and number fields

fmpzi.hGaussian integers \mathbb{Z}[i]: arithmetic, division with remainder, greatest common divisors, primality testing and polynomial multiplication.nf.hNumber fields \mathbf{Q}[x]/(f) given by a defining polynomial over \mathbf{Q}, with precomputed data for the arithmetic of nf_elem.h.nf_elem.hElements of number fields \mathbf{Q}[x]/(f), with special representations for linear and quadratic fields, arithmetic with delayed reduction, norms, traces, representation matrices and reduction modulo integers.qqbar.hAlgebraic numbers represented canonically by their minimal polynomial and an isolating ball, with exact arithmetic, comparisons, roots of polynomials, trigonometric values and conversion to closed forms.

Real and complex numbers

mag.hUnsigned floating-point numbers with a 30-bit mantissa for fast upper and lower boundsarf.hArbitrary-precision binary floating-point numbers with correct rounding and unbounded exponentsarb.hReal numbers as midpoint-radius balls with rigorous error propagationacb.hComplex numbers as rectangles of real balls, with rigorous arithmetic and elementary and special functionsacf.hComplex floating-point numbers as pairs of arf_t, for approximate computationarb_poly.hDense univariate polynomials and truncated power series with real ball coefficients, with rigorous multiplication, division, composition, evaluation, elementary and special functions of power series, and root refinement.acb_poly.hDense univariate polynomials and truncated power series with complex ball coefficients, with rigorous arithmetic, evaluation, composition, elementary and special functions of power series, and certified complex root finding.arb_fmpz_poly.hFunctions for integer polynomials that use real and complex balls: evaluation at balls, certified real and complex root isolation, deflation, and minimal polynomials of Gaussian periods.arb_mat.hDense matrices with real ball entries: rigorous arithmetic, verified solving of linear systems and inversion, determinants, Cholesky and LDL decompositions, the matrix exponential, and approximate floating-point linear algebra for preconditioning.acb_mat.hDense matrices with complex ball entries: rigorous arithmetic, verified solving and inversion, determinants, the matrix exponential, and certified eigenvalues and eigenvectors.arb_calc.hCalculus with real functions given by ball evaluators: rigorous isolation of the simple real roots of an analytic function by bisection, and refinement by bisection or interval Newton iteration.acb_calc.hRigorous numerical integration of complex functions along straight-line paths, combining direct interval enclosures, Gauss–Legendre quadrature with error bounds from analyticity, and adaptive subdivision.arb_fpwrap.hFloating-point wrappers of the real and complex special functions: double and complex double input and output with guaranteed accuracy, obtained by ball arithmetic with automatically increasing precision.

Special functions

arb_hypgeom.hGamma, error, exponential-integral, Bessel, Airy, Coulomb, Legendre and other hypergeometric functions of real ball arguments, with real-specific algorithms for the gamma and error functions, Legendre polynomials and their roots, and sums of hypergeometric series with rational parameters.acb_hypgeom.hRigorous evaluation of generalized hypergeometric functions and their special cases (gamma, error, exponential-integral, Bessel, Airy, Coulomb, Legendre, Gauss hypergeometric, orthogonal polynomials, dilogarithm) for complex ball and power series arguments.acb_elliptic.hComplete and incomplete elliptic integrals, Carlson symmetric integrals and Weierstrass elliptic functions of complex variables.acb_modular.hThe modular group, Jacobi theta functions, the Dedekind eta function, modular forms and Hilbert class polynomials.acb_theta.hRiemann theta functions and their derivatives in any genus, with a uniform quasi-linear algorithm, the Siegel modular group, and Siegel modular forms of degree 2.acb_dirichlet.hDirichlet L-functions, the Riemann and Hurwitz zeta functions, character sums, Hardy Z-functions and the zeros of the Riemann zeta function.acb_dft.hDiscrete Fourier transforms of complex ball vectors, as thin wrappers around gr_dft.

Floating-point arithmetic

nfloat.hPacked floating-point numbers with precision in whole wordsdfloat.hDouble-word to quad-double floating-point numbers and balls built on IEEE doublesmp_real.hLimb-radix multiple-precision real balls and fixed-point numbers, with the elementary functions, constants and hypergeometric series built on them.decimal.hArbitrary-precision decimal floating-point and ball arithmetic, real and complex, with correct rounding to a number of digits.double_extras.hHelper functions for double-precision floating-point numbersdouble_interval.hFast interval arithmetic with double endpointsd_vec.hVectors of double-precision floating-point numbersd_mat.hDense matrices of double-precision floating-point numbers

Exact real and complex numbers

calcium.hDefinitions shared by the exact real and complex number modules: triple-valued logic, output streams, function codes and hashing.ca.hExact real and complex numbers represented as elements of automatically constructed extension fields of the rationals, with special values, proved predicates, elementary and special functions.ca_vec.hVectors of exact real and complex numbers: memory management, entrywise arithmetic and zero tests.ca_poly.hDense univariate polynomials with exact real and complex coefficients: arithmetic, division, GCDs, power series, squarefree factorisation and roots.ca_mat.hDense matrices with exact real and complex entries: arithmetic, LU decomposition, solving, rank, determinants, characteristic polynomials, eigenvalues, Jordan forms and matrix functions.ca_ext.hExtension numbers, the generators of the fields in which exact real and complex numbers are represented: algebraic numbers, constants and function values, with cached enclosures.ca_field.hFormal fields Q(a_1, ..., a_n) generated by extension numbers, with their ideals of algebraic relations and the field cache of a context.fexpr.hSymbolic expressions stored in a flat-packed array of words, with construction, inspection, replacement, conversion to rational functions, plain-text and LaTeX output.fexpr_builtin.hThe builtin symbols of symbolic expressions, with their meaning and LaTeX rendering, and functions to look them up.

Generic rings

gr.hGeneric rings: context objects, elements, status codes and the generic interface to arithmetic in any ring.gr.hThe built-in rings and other structures of the generic interface, and their constructors.gr_generic.hThe default implementations of methods of the generic rings interface, and generic evaluation of integer polynomials.gr_special.hMathematical constants, elementary functions, combinatorial numbers and special functions over generic rings.gr_vec.hVectors over generic rings: memory management, elementwise arithmetic, dot products, sums and products, sorting and parsing.gr_mat.hDense matrices over any generic ring, with the generic algorithms for multiplication, LU and fraction-free LU decomposition, solving, determinants, ranks, echelon forms, characteristic polynomials, eigenvalues and matrix functions that FLINT's matrix modules build on.gr_poly.hDense univariate polynomials over any generic ring, with the generic algorithms for multiplication, division, GCDs, resultants, evaluation, composition, power series and factorisation over finite fields that most of FLINT's polynomial modules build on.gr_series.hGeneric rings of formal power series over any base ring - truncated power series modulo x^n, and power series with an error term O(x^n) tracked per element.gr_mpoly.hSparse multivariate polynomials over any generic ring, with heap-based multiplication and division (also multithreaded), division with remainder by ideals and pseudo-division, as a generic ring in its own right.gr_ore_poly.hDense univariate Ore polynomials (linear differential, difference, q-difference, Mahler and Frobenius operators) over generic rings, as a generic noncommutative ring.

Fast Fourier transforms

fft.hSchönhage–Strassen FFTs over \mathbb{Z}/(2^N + 1)\mathbb{Z} for multiplying large integers and polynomials with large integer coefficients.fft_small.hNumber-theoretic transforms modulo 50-bit primes computed in SIMD floating point, and the multimodular multiplication of integers and polynomials built on them.gr_dft.hDiscrete Fourier transforms of any length over generic rings, with rigorous fixed-point transforms of complex ball vectors.

@misc{flint-doc-index,
  author       = {{The FLINT team}},
  title        = {{FLINT documentation}},
  howpublished = {FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev},
  year         = {2026},
  url          = {https://flintlib.org/doc/},
  note         = {Generated 2026-10-20}
}