Brigitte Vallée (GREYC, CNRS)

L’algorithme d’Euclide, qui calcule le pgcd de deux entiers, est un des algorithmes de base en arithmétique. C’est l’un des plus anciens algorithmes de notre histoire et sa structure est très simple. Comme c’est le cas pour tous les algorithmes, on cherche à analyser précisément son comportement et à répondre à des questions naturelles sur sa complexité “en moyenne”: combien y-a-t-il d’itérations ? combien y-a-t-il de bits manipulés au total lors d’une exécution de l’algorithme? On se trouve alors confronté à de réelles difficultés, liées au fait que le déroulement de l’algorithme dépend de toute l’histoire précédente. C’est pourquoi l’analyse précise de son comportement n’a été établie que tout récemment, et fait appel à des méthodes mathématiques très variées, et pas toujours élémentaires….

J’exposerai en particulier un résultat très récent, obtenu en collaboration avec Viviane Baladi (Maths, Paris VII) qui montre que le nombre d’itérations et beaucoup de coûts naturels associés à l’algorithme suivent une loi qui est asymptotiquement gaussienne.