All the computations of the Gauss algorithm are done on the Gram matrices G([v.

2]), and the bit-complexity of the central part of the Gauss Algorithm is expressed as a function of

where p(u, v) is the number of iterations of the Gauss Algorithm.

The Gaussian algorithm for lattice reduction in dimension 2 is precisely analysed under a class of realistic probabilistic models, which are of interest when applying the Gauss algorithm "inside" the LLL algorithm.

The LLL algorithm uses as a main procedure the Gauss Algorithm.

This is why it is so important to have a precise understanding of the Gauss Algorithm.

It is then important to analyse the Gauss algorithm in a model where the skewness of the input bases may vary.

In this case, the Gauss Algorithm "tends" to the Euclidean Algorithm, and it is important to precisely describe this transition.

In this paper, we perform an exhaustive study of the main parameters of Gauss algorithm, in this scale of distributions, and obtain the following results:

Along the paper, we explain the role of the valuation r, and the transition phenomena between the Gauss Algorithm and the Euclidean algorithms which occur when r [right arrow] -1.

The LLL algorithm designed in [13] uses as a sub-algorithm the lattice reduction algorithm for two dimensions (which is called the Gauss algorithm) : it performs a succession of steps of the Gauss algorithm on the "local bases", and it stops when all the local bases are reduced (in the Gauss sense).

The positive Gauss algorithm aims at satisfying simultaneously the conditions (P) of Proposition 1.