Nous cherchons à analyser toute une classe d'algorithmes du pgcd,
de type Euclide.
Nous nous intéressons aux paramètres principaux de
l'algorithme, le nombre
d'itérations,
l'évolution des longueurs des restes, et aussi
la complexité en bits de l'algorithme, et
nous voulons décrire leur comportement ``moyen''.
Les méthodes classiques d'analyse
en moyenne sont maintenant bien établies, et beaucoup
reposent sur l'outil essentiel que
sont les séries génératrices. Pourtant,
dans le cas des
algorithmes d'Euclide, ces méthodes
ne peuvent s'appliquer, car la distribution des données
évolue de manière trop complexe
lors du déroulement de l'algorithme pour pouvoir être
traduite dans le formalisme des séries génératrices.
L'idée principale (et tout à fait naturelle)
consiste alors à considérer l'algorithme
et l'ensemble de ses données comme un système
dynamique. Dans l'étude ``classique" des systèmes dynamiques,
l'opérateur de transfert
est un outil très puissant qui permet de
décrire l'évolution du système. Dans le nouveau
contexte, cet opérateur prend le relais des
séries génératrices, et, après une
généralisation
naturelle et adéquate, il agit comme un
opérateur ``super-générateur",
au-dessus des séries
génératrices.
Nous décrivons le comportement moyen des principaux paramètres
décrits précédemment,
mais nous nous intéressons à leur distribution, et nous montrons que
la plupart d'entre eux
suivent une loi asymptotiquement gaussienne. Ces derniers résultats (en
distribution)
sont fondés sur une étude très fine de l'opérateur
de transfert, pour lequel nous montrons
l'existence d'une bande verticale sans pôle.