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.

This is why it is so important to have a precise understanding of the Gauss Algorithm. First, because this is a central algorithm, but also because it plays a primary role inside the LLL 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. The positive lattice reduction algorithm takes as input a positive arbitrary basis and produces as output a positive minimal basis.

On the input pair (u, v) = ([v.sub.0], [v.sub.1]), the positive Gauss Algorithm computes a sequence of vectors [v.sub.i] defined by the relations

The acute Gauss Algorithm. The acute reduction algorithm takes as input an arbitrary acute basis and produces as output an acute minimal basis.