## Links and references

### Software using FLINT

- Sage uses FLINT as the default package for polynomial arithmetic over Z, Q and Z/nZ for small n.
- Work is currently in progress to use FLINT in Singular, Macaulay2 and GAP.
- Scarab library - an implementation of fully homomorphic encryption using FLINT.
- Nemo - a computer algebra package for the Julia programming language
- HFlint - a FLINT wrapper for Haskell

### References to FLINT in the literature and online

- Practical divide-and-conquer algorithms for polynomial arithmetic - W. Hart and A. Novocin
- Efficient implementation of the Hardy-Ramanujan-Rademacher formula - F. Johansson
- A fast algorithm for reversion of power series - F. Johansson
- An introduction to FLINT (pp. 88-91) - W. Hart
- Arb: Efficient Arbitrary-Precision Midpoint-Radius Interval Arithmetic - F. Johansson
- FLINT 2 benchmarking - F. Johansson
- Fast special function computations with FLINT - F. Johansson (Talk)
- Practical polynomial factoring in polynomial time - W. Hart, M. van Hoeij, A. Novocin
- Algorithms for finite field arithmetic (ISSAC 2015) - E. Schost
- Parallel sparse interpolation using small primes (PASCO 2015) - M. Khoctali, D. Roche, X, Tian
- Modular SIMD arithmetic in Mathemagix - J. van der Hoeven, G. Lecerf
- There are no two non-real conjugates of a Pisot number with the same imaginary part - A. Dubickas, K. Hare, J. Jankauskas
- Fast arithmetic for matrices and polynomials in Mathemagix - G. Lecerf
- Can you save time in multiplying polynomials by encoding them as integers? - R. Fateman
- Algorithm implementations in a software library - D. Roche (Chapter PhD. Thesis)
- Practical Cryptanalysis of ISO/IEC 9796-2 and EMV Signatures - J-S Coron, D. Naccache, M. Tibouchi, R-P Weinmann
- A cache-friendly truncated FFT - David Harvey
- Techniques for Performance Improvement of Integer Multiplication in Cryptographic Applications - R. Brumnik, V. Kovtun, A. Okhrimenko, S. Kavun
- Relaxed algorithms for p-adic numbers - Jeremy Berthomieu, Joris van der Hoeven, Gregoire Lecerf
- Nullspace computation over rational function fields for symbolic summation - B. Erocal, A. Storjohann (ISSAC poster)
- Experimental evidence for Maeda's conjecture on modular forms - A. Ghitza, A. McAndrew
- Fast polynomial evaluation and composition - Guillaume Moroz
- HLinear: Exact Dense Linear Algebra in Haskell - Alex Ghitza and Martin Westerholt-Raum
- Poster about parallel factorisation - Ammon Bartram
- Talk : Sage for Mathematical and Cryptographic Research - Martin Albrecht and William Stein
- Talk : Sage for Number Theorists - William Stein
- Basic Polynomial Algebra Subprograms - C. Chen, S. Covanov, F. Mansouri, M. Maza, N. Xie, Y. Xie
- Oberwolfach References on Mathematical Software.
- Talk: Sage : What is on the Horizon - William Stein
- Poster about Factoring Algorithms over Finite Fields - Richard Howell-Peak
- Grant Proposal - William Stein
- Number Theory Web - Number theory ftp sites/calculator programs/archives - Keith Matthews
- Talk : Fast Integer Multiplication with Schoenhage-Strassen's Algorithm - Alexander Kruppa
- Wikipedia Article : Fast Library for Number Theory.
- Poster about Efficiently computing Bernoulli numbers using FLINT - David Howden
- Grant Proposal - William Stein
- Poster about Implementing Middle Product in FLINT - Daniel Scott
- Poster about p-adic Arithmetic - Daniel Ellam
- Programas utiles para Mathematica - Pablo De Napoli
- Implementation of new polynomial factoring algorithm - van Hoeij, Novocin, Hart.
- Methods and implementations for integer factorization (slides) - D. Jacobsen.
- Using the FLINT FFT for (string) pattern matching - B. Smithers
- The zn_poly library - D. Harvey
- Factory library - M. Lee, O. Motsak

### Mathematics, algorithms and implementation

The following list is incomplete. More references can be found in the FLINT documentation.

- Bernstein - Composing power series, especially over ring with small characteristic
- Kaltofen and Shoup - Probabilistic algorithm for factoring univariate polynomials over a finite field
- Victor Shoup - A discussion of various factoring algorithms over finite fields
- Joris van der Hoeven - Relaxed Multiplication Using the Middle Product
- Joris van der Hoeven - New algorithms for relaxed multiplication
- Joris van der Hoeven - Relax but don't be too lazy
- Damien Stehle - A very detailed paper describing the many tricks for speeding up LLL in floating point
- A thesis on the general number field sieve
- Dan Bernstein - A detailed paper describing the algebra of every known multiprecision multiplication algorithm including many FFT tricks
- Dan Bernstein - A detailed paper describing a very many algorithms for real, padic and multiprecision arithmetic
- A very useful page on primality proving
- Arnold Schonhage - A paper describing some clever tricks for polynomial division
- Sam Wagstaff, Jason Gower - Very useful paper on SQUFOF and various heuristics associated with it
- Eric Landquist - Excellent paper by an acquaintance of mine, on the quadratic sieve
- Tutorial on using OpenMP
- Old article on doing exact rational arithmetic with "finite segment" p-adic arithmetic. Better for division than multimodular arithmetic.
- Another paper on Hensel codes and finite segment p-adic arithmetic, but not much different to the above.
- A further paper on Hensel codes and finite segment p-adic arithmetic, correcting numerous errors in previous work on the subject.
- Yet another very old paper on Hensel codes, this time with applications to matrix algebra over Q.
- Paul Hsieh - Excellent description of various algorithms for computing floating point and integer square roots efficiently.
- Michael Backes - Masters thesis on univariate polynomial factorisation.
- Harald Niederreiter - Algorithm for factoring polynomials over finite fields.
- Harald Niederreiter, Rainer Gottfert - Algorithm for factoring polynomials over finite fields.
- Julio Genovese - Improvement of the Berlekamp/Niederriter algorithms for factoring polynomials over finite fields.
- Victor Shoup, Joachim von zur Gathen - Frobenius and trace map algorithm for factoring polynomials over finite fields.
- Brillhart, Lehmer, Selfridge - Numerous primality proving algorithms.
- Gao, Panario - Numerous algorithms for testing irreducibility of polynomials.
- Panario, Pittel, Richmond, Viola - Analysis of Rabin's irreducibility test for polynomials.
- Gashkov, Gashkov - Improvements for Rabin's polynomial irreducibility test.
- Umans - Fast modular composition (f(g(x)) modulo h(x)) over Z/pZ and asymptotically fast polynomial factorisation.
- Yap, Thul - Half GCD algorithm for both integers and polynomials.
- David Harvey - A paper detailing two new algorithms for Kronecker Segmentation, called KS2 and KS4.
- Bernard Parisse - Details a proven bound for the heuristic gcd algorithm for polynomials (univariate and multivariate).
- van Hoeij, Novocin - Improvements in factoring polynomials over Z.
- van Hoeij, Novocin, Hart - Implementation of new polynomial factoring algorithm.
- Novocin, Stehle, Villard - Quasi-linear LLL.

*Last updated: 2019-10-17 12:47:54 GMT*

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