Algorithmique de la réduction de réseaux et application à la recherche de pires cas pour l'arrondi de fonctions mathématiques.

The manuscript (in French): ps.gz, pdf.
The slides of the defense (in French): ps.gz, pdf.


President: Brigitte VALLÉE
Reviewers: François MORAIN
Examiners: Peter MARKSTEIN
Paul ZIMMERMANN (PhD supervisor)


Euclidean lattices are a particularly powerful tool for several algorithmic topics, among which are cryptography and algorithmic number theory. The contributions of this thesis are twofold: we improve lattice basis reduction algorithms, and we introduce a new application of lattice reduction, in computer arithmetic. Concerning lattices, we consider both small dimensions (in dimension one, where the problem degenerates to a gcd calculation, and in dimensions 2 to 4), and arbitrary dimensions, for which we improve the classical LLL algorithm. Concerning the application, we make use of Coppersmith's method for computing the small roots of multivariate modular polynomials, in order to find the worst cases for the rounding of mathematical functions, when the function, the rounding mode and the precision are fixed. We also generalise our technique to find input numbers that are simultaneously bad for two functions. These two methods are expensive pre-computations, but once performed, they help speeding up the implementations of elementary mathematical functions in fixed precision, for example in double precision.
Most of the algorithms described in this thesis have been validated experimentally. These implementations are available at the url

Part I: Preliminaries.

I-1. Some background in the geometry of numbers.

I-2. Some background in floating-point arithmetic.

Part II: Lattice reduction algorithms.

II-1: A recursive binary gcd algorithm.

Here are some experimental results on the generalizes binary division.
These results heve been validated theoretically by an average case analysis due to Daireaux, Maume-Deschamp and Vallée.

II-2: Lattice reduction in small dimension.

III-3: The floating-point LLL algorithm.

Here is a 55-dimensional lattice basis that makes NTL's LLL_FP loop forever, with delta=0.99.
This basis also makes Magma's LLL loop, once some options have been removed:
M:= LLL(L: InitialSort := false, Delta := 0.99, UseGram:= false, UnderflowCheck:=false , Large := false);

Here is a 55-dimensional lattice basis for which NTL's LLL_FP (with delta=0.99) realizes that the floating-point calculations are incorrect, and restarts the computation with a larger precision.

III-4: Experimental results on the LLL algorithm.

The library fplll-1.2.
Some libraries containing an implementation of the LLL algorithm:
NTL, Magma, Pari GP, LiDIA.

Exerimental data corresponding to the figures of this chapter:
fig4.2, fig4.2bis,
fig4.4, fig4.4bis,
fig4.5a, fig4.5b, fig4.5c, fig4.5d,
fig4.7a, fig4.7b.

Here is an 83-dimensional lattice basis that makes the proved variant of fplll-1.2 loop forever, once the precision has been fixed to 113 bits (quadruple precision), with delta=0.99.
Here is a 3-dimensional lattice basis that makes NTL's G_LLL_FP loop forever, with delta=0.99.

Part III: Worst cases for the rounding of mathematical functions.

III-1: The search for worst cases of mathematical functions.

The code corresponding to the algorithm described in this chapter: wclr-1.1.

III-2: Improving Gal's method.

The code corresponding to the algorithm described in this chapter: gatmr-1.0.
First table for 2^x.
Table for sin x.
Second table for 2^x.

III-3: Cryptanalysis of Littlewood's PRNG.