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é)
[development version] and
Also contains code to search for irreducible trinomials over GF(2)
[replaces and superseedes the irred-ntl code].
mul_fft-126.96.36.199.tgz, a GMP-based implementation of
Schönhage-Strassen's large integer multiplication algorithm
(with Pierrick Gaudry and Alexander Kruppa). This code is 27%
faster than the one distributed within GMP 5.0.1. 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.
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.