## Features

FLINT is a collection of modules, with an interface
similar to that of the GMP library.
For example, the FLINT `fmpz_poly` module defines
the `fmpz_poly_t` type (representing a polynomial with multiprecision integer coefficients)
and provides methods such as `fmpz_poly_add`, `fmpz_poly_gcd`, etc.

### FLINT modules

The following is a list of modules available in FLINT version 2.6, and a summary of the features and algorithms in each module. Besides the features listed explicitly, each module implementing a specific type also provides methods for arithmetic operations (add, sub, mul and so on), conversions between types, random generation, and printing. Some utility modules are omitted from the list.

#### flintxx - C++ wrapper

- Provides an object-oriented interface with operator overloading
- Exposes most of the FLINT C functions
- Uses C++98 expression templates to avoid temporary allocations and assignments, usually giving the same performance as hand-written C code

#### ulong_extras - functions for word-size integers

- Functions work with unsigned integers all the way up to 32/64 bits
- Division and modular arithmetic using precomputed inverses
- Random number generation
- Memory-efficient generation of primes (block sieve of Eratosthenes)
- Fast factorisation (trial division, Hart's one line algorithm, SQUFOF)
- Fast primality proving (verified BPSW test, Pocklington, pseudosquare)
- Probable prime tests (BPSW, Fermat, Fibonacci, Lucas)
- Square roots and modular square roots
- Number-theoretic functions (GCD, Jacobi symbol, Euler phi, etc.)
- Fast cube and nth root computation

#### qsieve - small quadratic field

- Efficient factorisation of integers up to two words (64 or 128 bits)

#### fft - optimised Schönhage-Strassen FFT

- Cache friendly up to huge transforms (integers of billions of bits)
- Truncated -- no uglytwit performance jumps at power of 2 lengths and no problem with unbalanced multiplications
- Truncated FFT/IFFT functions can be used for polynomial multiplication
- Extremely fast (up to 30% faster than MPIR 2.4.0 and 70% faster than GMP 5.0.2 on a 2.2GHz AMD K10-2)
- Easy to tune
- This module is BSD licensed

#### fmpz - multiprecision integers

- Tagged pointer representation, with integers up to 30 or 62 bits only using a single word and not requiring heap allocation
- Caches larger integers for fast allocation and deallocation
- Very efficient for small integers, and similar performance to the mpz type for large numbers
- GCD, XGCD, LCM, Jacobi symbol, modular inverse, modular square roots
- Factorials, Fibonacci numbers, binomial coefficients, rising factorials
- Asymptotically fast multimodular reduction and Chinese remaindering via subproduct trees
- Pseudosquare primality test
- Primality testing (Pocklington, Morrison)
- Probable primality testing (Lucas, Baillie-PSW, strong-psp, Brillhart-Lehmer-Selfridge)

#### fmpz_factor - factoring multiprecision integers

- Factors 32/64-bit integers quickly via ulong_extras
- Trial division
- Williams' p + 1 method
- ECM
- Self initialising, large prime variant quadratic sieve

#### fmpz_mat - dense matrices over the integers

- Classical and multimodular multiplication
- Fast nonsingular solving (fraction-free, Dixon p-adic lifting)
- Fast determinants (fraction-free, multimodular)
- Reduced row echelon form, nullspace, inverse (fraction-free)
- Characteristic polynomial
- Hermite normal form (naive, xgcd, Domich-Kannan-Trotter, Kannen-Bachem, Pernet-Stein)
- Smith normal form (diagonal, Kannen-Bachem, Iliopoulos)

#### fmpz_lll - LLL

- LLL (rational, Nguyen-Stehle, from Gram matrix, with_removal, Storjohann/ULLL)

#### fmpz_mod_poly - dense univariate polynomials over Z/nZ for multiprecision n

- Fast arithmetic based on the fmpz_poly module
- Divide-and-conquer division and composition
- GCD and XGCD (Euclidean, half GCD)
- Fast modular composition (Brent-Kung)
- Fast multipoint evaluation

#### fmpz_mod_poly_factor - factoring in (Z/nZ)[x] for multiprecision n

- Berlekamp, Cantor-Zassenhaus, Kaltofen-Shoup algorithms
- Squarefree, distinct-degree and equal-degree factorisation

#### fmpz_mod_mat - matrices over Z/nZ for multiprecision n

- Basic arithmetic

#### fmpz_poly - dense univariate polynomials over the integers

- Embarrassingly fast multiplication (classical, Karatsuba, Kronecker substitution, Schönhage-Strassen)
- Efficient truncated products (power series multiplication)
- Evaluation and composition (Horner, divide-and-conquer)
- Basecase and divide-and-conquer division and pseudodivision
- Power series composition (Brent-Kung) and reversion (fast Lagrange)
- Powering (binary algorithm, multinomial coefficients)
- Taylor shift (basecase, divide-and-conquer)
- GCD and XGCD (heuristic, multimodular), resultants
- Restartable Hensel lifting
- Interpolation, Chinese remaindering, bit packing

#### fmpz_poly_factor - factoring in Z[x]

- Squarefree factorisation
- Zassenhaus algorithm

#### fmpz_poly_mat - matrices over Z[x]

- Multiplication (classical, Kronecker substitution)
- Determinants (fraction-free, interpolation)
- Reduced row echelon form, nullspace, inverse (fraction-free)

#### fmpz_poly_q - rational functions over Q

- Efficient arithmetic based on the fmpz_poly module

#### fmpz_mpoly - multivariate polynomials over Z

- Efficient arithmetic for polynomials in sparse distributed form

#### fmpq - multiprecision rational numbers

- Based on the fmpz type -- efficient representation of small rational numbers, and similar performance to the mpq type for large numbers
- Rational reconstruction (balanced or unbalanced)
- Conversion from continued fraction (subquadratic) and to continued fraction
- Enumeration of the rationals (minimal height, Calkin-Wilf tree)

#### fmpq_mat - dense matrices over the rational numbers

- Efficient multiplication, determinants and nonsingular solving dona via the integers
- Reduced row echelon form (naive)

#### fmpq_poly - dense univariate polynomials over the rational numbers

- Efficient representation with a single denominator, basing most operations on the fmpz_poly module
- Fast multiplication, division, composition, powering, GCD, XGCD, LCM done via the integers
- Fast power series composition and reversion
- Functions of power series (inverse, sqrt, exp, log, sin, asin, ...)

#### fmpq_mpoly - multivariate polynomials over Q

- Efficient arithmetic for polynomials in sparse distributed form

#### nmod_mat - matrices over Z/nZ for word-size n

- Classical and multimodular multiplication
- Fast multiplication (reduction-free basecase, Strassen)
- Block recursive LU decomposition, reduced row echelon form, nullspace, inverse
- Determinant, rank, trace

#### nmod_poly - dense univariate polynomials over Z/nZ for word-size n

- Embarrassingly fast multiplication (classical, Kronecker substitution, David Harvey's KS2 and KS4)
- Fast division (basecase, divide-and-conquer, Newton)
- Divide-and-conquer composition
- Fast GCD and XGCD (Euclidean, half gcd)
- Fast modular composition
- Fast multipoint evaluation and interpolation
- Fast Taylor shift (basecase, convolution)
- Fast power series composition and reversion (Brent-Kung, fast Lagrange)
- Functions of power series (inverse, sqrt, exp, log, sin, asin, ...)

#### nmod_mod_poly_factor - factoring in (Z/nZ)[x] for word-size n

- Berlekamp, Cantor-Zassenhaus, Kaltofen-Shoup algorithms
- Squarefree, distinct-degree and equal-degree factorisation
- Irreducibility testing
- Power hack for polynomials of special form

#### nmod_poly_mat - matrices over Z/nZ[x] for word-size n

- Multiplication (classical, Kronecker substitution, interpolation)
- Determinants (fraction-free, interpolation)
- Reduced row echelon form, nullspace, inverse (fraction-free)

#### nmod_mpoly - multivariate polynomials over Z/nZ

- Efficient arithmetic for polynomials in sparse distributed form

#### padic - p-adic numbers

- Efficient representation based on the fmpz type
- Inverse and square root (Newton iteration)
- Exp and log (rectangular splitting, binary splitting)
- Teichmuller lift

#### padic_poly - polynomials over the p-adic numbers

- Efficient representation based on the fmpz_poly module

#### padic_mat - matrices over the p-adic numbers

- Efficient representation based on the fmpz_mat module

#### qadic - unramified extensions of the p-adic numbers

- Standardised representation using Conway polynomials
- Inverse and square root (Newton iteration)
- Exp and log (rectangular splitting, binary splitting)
- Teichmuller lift

#### fq / fq_nmod / fq_zech - finite fields F_q

- Three implementations optimised for different sizes: multi-precision primes, single-precision primes, and Zech logarithms
- Construction of finite fields using Conway polynomials or user-defined polynomials
- Powers, roots, Frobenius map, trace
- Bit packing

#### fq_mat / fq_nmod_mat / fq_zech_mat - dense matrices over finite fields F_q

- Classical and Kronecker substitution matrix multiplication
- Block recursive LU decomposition, reduced row echelon form, solving

#### fq_poly / fq_nmod_poly / fq_zech_poly - dense univariate polynomials over finite fields F_q

- Fast multiplication (classical, reordering, Kronecker substitution)
- Fast division (basecase, divide-and-conquer, Newton)
- Divide-and-conquer composition
- Fast GCD and XGCD (Euclidean, half gcd)
- Fast modular composition (Brent-Kung)

#### fq_poly_factor / fq_nmod_poly_factor / fq_zech_poly_factor - factorisation of polynomials over F_q

- Berlekamp, Cantor-Zassenhaus, Kaltofen-Shoup algorithms
- Squarefree, distinct-degree and equal-degree factorisation
- Irreducibility testing

#### fq_nmod_mpoly - multivariate polynomials over finite fields

- Efficient arithmetic for polynomials in sparse distributed form

#### arith - miscellaneous arithmetic functions

- Bernoulli, Euler, Bell, Stirling numbers
- Fast computation of the integer partition function
- Divisor sum, Euler phi and Möbius mu functions
- Sum of squares counting
- Cyclotomic, Chebyshev, Legendre, Swinnerton-Dyer polynomials
- Dedekind sums

### Antic library

The Antic library adds support for algebraic number theory. Antic includes the following modules.

#### qfb - binary quadratic forms

- Fast composition (Shanks' NUCOMP, NUDUPL)
- Computation of reduced forms
- Computation of the exponent of the class group (rigorously or assuming GRH)

#### nf_elem - elements of number fields

- Fast number field arithmetic based on the FLINT fmpq_poly type

### Arb library

The Arb library adds support for fast arbitrary-precision real and complex numbers with rigorous error control (using ball interval arithmetic). It supports polynomials, power series, matrices, and evaluation of special functions. Arb includes the following modules.

#### fmpr - binary floating-point numbers

- Efficient representation at word-size precision (up to 30/62 bits)
- Dynamic allocation, supporting integer-valued numbers efficiently
- Supports arbitrary-precision exponents
- Supports correct directed rounding (up/down/floor/ceiling)

#### fmprb - real numbers represented as floating-point balls

- All operations support arbitrary precision with automatic, rigorous error bounds
- Interval predicates (is positive, contains unique integer, etc.)
- Mathematical constants (pi, e, gamma, Catalan, ...)
- Elementary functions (sqrt, pow, exp, log, sin, ...)
- Rapid computation of special trigonometric values
- Special functions (gamma, digamma, log gamma, rising factorials, Riemann zeta function)

#### fmpcb - complex numbers

- Complex floating-point arithmetic based on the fmprb type
- All operations support arbitrary precision with automatic, rigorous error bounds
- Interval predicates
- Elementary functions (sqrt, pow, exp, log, sin, ...)
- Rapid computation of roots of unity
- Special functions (gamma, digamma, log gamma, rising factorials, Riemann zeta function, Hurwitz zeta function)

#### fmprb_poly - polynomials over the real numbers

- All operations support arbitrary precision with automatic, rigorous error bounds
- Numerically stable fast multiplication (scaling and blockwise multiplication over Z[x])
- Efficient truncated (power series) multiplication
- Fast division and power series division (Newton iteration)
- Composition (divide and conquer)
- Power series composition (Brent-Kung) and reversion (fast Lagrange)
- Evaluation (Horner, Paterson-Stockmeyer)
- Fast multipoint evaluation and interpolation
- Borel and binomial transforms
- Power series of elementary functions (sqrt, pow, exp, log, sin, ...)
- Power series of special functions (gamma, digamma, log gamma, rising factorials, Riemann and Hurwitz zeta functions, Riemann-Siegel theta and Z-functions)
- Asymptotically fast root polishing

#### fmpcb_poly - polynomials over the complex numbers

- All operations support arbitrary precision with automatic, rigorous error bounds
- Numerically stable fast multiplication (real decomposition)
- Fast division and power series division (Newton iteration)
- Composition (divide and conquer)
- Power series composition (Brent-Kung) and reversion (fast Lagrange)
- Evaluation (Horner, Paterson-Stockmeyer)
- Fast multipoint evaluation and interpolation
- Power series of elementary functions (sqrt, pow, exp, log, sin, ...)
- Power series of special functions (gamma, digamma, log gamma, rising factorials, Riemann and Hurwitz zeta functions)
- Isolation of all complex roots (Durand-Kerner iteration followed by verification)

#### fmprb_mat - matrices over the real numbers

- All operations support arbitrary precision with automatic, rigorous error bounds
- Multithreaded matrix multiplication
- LU decomposition
- Nonsingular solving, inverse, determinant

#### fmpcb_mat - matrices over the complex numbers

- All operations support arbitrary precision with automatic, rigorous error bounds
- LU decomposition
- Nonsingular solving, inverse, determinant

#### fmprb_calc - calculus with real-valued functions

- Rigorous isolation of roots (interval bisection)
- Asymptotically fast root polishing (Newton iteration with rigorous error bounds)

#### fmpcb_calc - calculus with complex-valued functions

- Numerical integration (Taylor algorithm with rigorous error bounds)

*Last updated: 2021-07-23 11:05:42 GMT*

*Contact: William Hart, flint-devel mailing list.*