Benoît Daireaux: Dynamical Analysis of the Truncated Euclidean Algorithm

This is a joint work with Brigitte Vallée.

The Lehmer-Euclid algorithm is a well-known improvement of the Euclid algorithm when applied to large integers. This algorithm can be viewed as a sequence of "truncated" Euclidean algorithms. These Euclidean algorithms are called "truncated" because their execution is stopped as soon as the current integers are sufficiently small with respect to the input integers (for instance the length of the current integer is smaller than the half of the input length). Our final purpose is the analysis of the Lehmer-Euclid algorithm; here, we provide a complete analysis of the truncated Euclid algorithm and study its main parameters: number of iterations, bit-complexity, and distribution of the output configurations. We perform that we call a "dynamical analysis", i.e., an analysis where the algorithm is viewed as a "dynamical system". Generating functions are then replaced by "generating operators", and singularity analysis is replaced by a spectral analysis of these operators. Our results generalize previous results that Vallée obtained in the case of the "complete" Euclid algorithm. This analysis is a first important step towards the complete analysis of Lehmer-Euclid algorithm.

Back to the Index


Please send comments and corrections to Thomas Klausner.