Séminaire LJKModèles et Algorithmes Déterministes: CASYS

Le Mardi 19 Décembre 2017 à 14h00 en Amphithéâtre  RDC  Tour IRMA

Séminaire de Mr Thomas ESPITAU (UPMC)

Certified lattice reduction, with a view towards algebraic number theory

Résumé:

Quadratic form reduction and lattice reduction are fundamental tools in computational number theory and in computer science, especially in cryptography. The celebrated LenstraLenstraLovász reduction algorithm (socalled 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 floatingpoint variantswhere the longinteger arithmetic required by GramSchmidt orthogonalization is replaced by floating point arithmeticare now the fastest known. Nonetheless, the systematic study of the reduction theory of real quadratic forms or more generally of real latticesin particular on the precision needed to represent lattices in such a way the reduction can soundly operateis quasiinexistent. In this talk, we present a sound adaptiveprecision 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, floatingpoint 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.
