Average Bit-Complexity of Euclidean Algorithms

We obtain new results regarding the precise average bit-complexity of algorithms of a broad Euclidean type. We analyze the main quantities---digits and continuants---that intervene in an entire class of gcd-like algorithms. We develop a general framework for the analysis of such algorithms, where the average-case complexity of an algorithm is related to the analytic behaviour in the complex plane of the set of elementary transformations determined by the algorithms. The methods rely on properties of transfer operators suitably adapted from dynamical systems theory. They use a general transfer from the continuous case (Continued Fraction Algorithms) to the discrete case (Euclidean Algorithms), where Ergodic Theorems are replaced by Tauberian Theorems. Joint Work with Ali Akhavi, GREYC, Caen University.