FLINT: Fast Library for Number Theory

FLINT is a C library for doing number theory, maintained by William Hart. FLINT is licensed GPL v2+.

News

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

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.

Download

For a list of changes, see the NEWS file.

FLINT 2.x series: FLINT 1.x series:

Development

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:

https://github.com/wbhart/flint2

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

Features

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
Polynomials
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:

Code Example

The following program computes and prints (2 + 3x + 5x2 + 7x3 + 11x4)2. A few more example programs can be found in the examples directory.

#include <stdio.h>
#include "flint.h"
#include "fmpz_poly.h"
#include "ulong_extras.h"

int main()
{
    int i;
    fmpz_poly_t f, g;
    fmpz_poly_init(f);
    fmpz_poly_init(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);
    fmpz_poly_print_pretty(g, "x");

    fmpz_poly_clear(f);
    fmpz_poly_clear(g);
}

Contributors

Main authors

International Colleagues

Undergraduate Student Projects

Additional Contributors

Links and References

Software using FLINT

References to FLINT in the Literature and Online

Mathematics, Algorithms and Implementation

Some more references can be found in the FLINT documentation.

This site is hosted at sage.math.washington.edu thanks to William Stein.