Cohérence Territoriale Et Cohésion Sociale Tome 1

Euclidean lattices are a rich algebraic object that occurs in a wide variety of contexts in mathematics and in computer science. The present thesis considers several algorithmic aspects of lattices. The concept of lattice basis reduction is thoroughly investigated: in particular, we cover the full range of time-quality trade-offs of reduction algorithms. On the rst hand, we describe and analyse fast algorithms for nding a relatively short basis (LLLreduced basis) of an arbitrary given lattice. On the second hand, we propose novel analyses for (slower) algorithms that compute very short bases (HKZ-reduced and BKZ-reduced bases). This study on how to ef ciently solve algorithmic problems on lattices is completed by a constructive application exploiting their apparent hardness. We propose and analyze cryptographic schemes, including the NTRU encryption function, and prove them at least as secure as well-speci ed worst-case problems on lattices.