Main software tools.
- CADO-NFS, an implementation
of the number field sieve for integer factorization, registered at APP
under number IDDN.FR.001.150006.000.S.P.2010.000.10000.
a library for multiplication in GF(2)[x] (with Richard P. Brent,
Pierrick Gaudry and Emmanuel Thomé).
Also contains code to search for irreducible trinomials over GF(2)
[replaces and superseedes the irred-ntl code].
mul_fft-6.1.2.tgz, a GMP-based implementation of
Schönhage-Strassen's large integer multiplication algorithm
(with Pierrick Gaudry and Alexander Kruppa). This code is up to
faster than the one distributed within GMP 6.1.2. It was used by
Andrew Sutherland to set a new record for
point-counting over a prime field.
See also the mirror
on Gaudry's web page.
A fixed-length FFT code is
also available for length 26
[see corresponding mail].
an implementation of Lenstra's Elliptic Curve Method to factor integers.
See also the
a library for multiprecision complex arithmetic with exact rounding,
based on the MPFR and GNU MP libraries [with
Andreas Enge, Philippe Théveny
and Patrick Pélissier]
- MPFR: a library for multiple-precision
floating-point computation with correct rounding
[compiler bugs revealed by MPFR]
Other software tools.
- hjacobi.c implements an O(M(n) log n) algorithm
for the Jacobi symbol (joint work with Richard Brent).
- double_fac_ui.c implements the
double factorial (see this and that).
- WCLR implements the algorithm described
in the articles Worst Cases and Lattice Reduction
(with Vincent Lefèvre). It is now superseeded by
(with Guillaume Hanrot, Vincent Lefèvre, and Damien Stehlé)
a library for floating-point arithmetic with large exponents
(double-precision + exponent), developed with Patrick Pélissier.
[Software Heritage archive, cf this
a generic spell-checking mechanism, including a french dictionary
(but it can be used for any language, as soon as you have a dictionary).
- intersectplot.mpl, a Maple program to
plot the intersection of two 3D surfaces given by implicit equations
(with Sylvain Petitjean)
- An implementation of LLL in GMP, translated from that
from the NTL library from Victor
Lambda-Upsilon-Omega V2.1, an automatic average-case program analyzer
developed with Bruno Salvy. This version corrects a problem with
See also the LUO page from the Algo project.
- MPCHECK 1.1.0, with Nathalie Revol
and Patrick Pélissier, a program to check mathematical function
libraries (correct rounding, monotonicity, symmetry, output range).
Warning: version 1.1.0 only works for the double type (53 bits).
- A sample implementation of MPQS,
reusing some nice sieving code written by
- MuPAD, a symbolic computation system
I have contributed to in 1994-1995. Unfortunately it never became free,
contrary to what was originally planned.
- A program for digital plane
recognition (with Yan Gérard and Isabelle Debled-Rennesson)
- An implementation of PSLQ in GMP.
- shift2.c, a implementation in GNU MP of an
asymptotically fast algorithm for Taylor shift. Werner Krandick reports
a speedup factor of 319 for degree 9,000 and coefficients of 9,000 bits,
over von zur Gathen's and Gerhard's convolution method.
This work was inspired by
High-Performance Implementations of the Descartes Method, by
Jeremy R. Johnson, Werner Krandick, Kevin M. Lynch, David G. Richardson,
and Anatole D. Ruslanov.
- An implementation in GMP of the
algorithm for Toom-Cook 4-way.
Bodrato and Zanoni extended this to
Toom-Cook 5-way, 6-way
- A GMP-based implementation of Uspensky's algorithm
(joint work with Fabrice Rouillier)
to isolate all real roots of a polynomial with integer coefficients.
A revised implementation
is available in CADO-NFS
(directory utils, file usp.c).
You might also check the file src/libqi/kernel/QISolve.cc from
the QI library.