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 |

Gilles VILLARD | |

Examiners: | Peter MARKSTEIN |

Gérald TENENBAUM | |

Paul ZIMMERMANN (PhD supervisor) |

Most of the algorithms described in this thesis have been validated experimentally. These implementations are available at the url http://www.loria.fr/~stehle.

These results heve been validated theoretically by an average case analysis due to Daireaux, Maume-Deschamp and Vallée.

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.

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.3,

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.

First table for 2^x.

Table for sin x.

Second table for 2^x.