Résumé : The computation of GCDs or inverse modulars is a basic operation in Arithmetic or Cryptography. The analysis and the optimisation of algorithms that compute GCDs is a speciality in Caen. In this talk, we will introduce two multiple Gcd algorithms that are natural extensions of the usual Euclid algorithm, and coincide with it for two entries. The plain (or naive) algorithm was proposed by Knuth and performs successive calls to the classical Euclid Algorithm. The Brun algorithm performs Euclidean divisions, between the largest entry and the second largest entry, and then re-orderings. This is the discrete version of a multidimensional continued fraction algorithm due to Brun. We will present the average--case analyses of the plain and the Brun algorithms. Both analyses are very similar and we will prove that the mean number of Euclidean divisions is linear with respect to the input size. However, we show that the role of the dimension is different according to the algorithm. The method relies on dynamical analysis, and is based on the study of the underlying dynamical systems.

Dernière modification : Thursday 21 November 2024

Contact pour cette page : Cyril.Banderier at lipn.univ-paris13.fr