Certified lattice reduction, with a view towards algebraic number theory

Quadratic form reduction and lattice reduction are fundamental tools in computational number theory and in computer science, especially in cryptography. The celebrated Lenstra-Lenstra-Lovász reduction algorithm (so-called LLL) has been improved in many ways through the past decades and remains one of the central method used for reducing integral lattice basis. In particular, its floating-point variants--where the long-integer arithmetic required by Gram-Schmidt orthogonalization is replaced by floating- point arithmetic--are now the fastest known. Nonetheless, the systematic study of the reduction theory of real quadratic forms or more generally of real lattices--in particular on the precision needed to represent lattices in such a way the reduction can soundly operate--is quasi-inexistent. In this talk, we present a sound adaptive-precision version of a generalized LLL algorithm working for lattices endowed with an arbitrary scalar product, as well as a theoretical analysis of the representation needed to perform such a reduction. In this framework, floating-point arithmetic is replaced by Interval Arithmetic. The inherent certification property of Interval Arithmetic enables runtime detection of precision defects in numerical computations and accordingly makes it possible to run the reduction algorithms with guaranteed nearly optimal precision. We then present some applications of these results to algebraic number theory and more precisely develop sound techniques for an algorithmic insight of the Geometry of Numbers in number fields.