Damien Stehlé (INRIA Nancy)

Les algorithmes usuels de PGCD, comme l’algorithme d’Euclide et l’algorithme binaire, ont des complexités quadratiques en la taille des entiers considérés. En 1970, Knuth a proposé un algorithme en temps quasi-linéaire (de complexité O(n log2 log log n), cette borne a été prouvée par Schonhage), qui repose sur la multiplication rapide d’entiers, à base de FFT. Cet algorithme est une variante récursive de l’algorithme d’Euclide. Malgré sa bonne complexité asympotique, il n’est intéressant que pour de très grands nombres, à cause de l’utilisation interne d’une routine très coûteuse de “réparation locale” des quotients calculés. Dans cet exposé, nous présenterons un algorithme récursif basé non pas sur la division Euclidienne classique mais sur une generalisation de la division binaire. Il a la même structure et la même complexité asymptotique que l’algorithme de Knuth, mais il n’y a plus besoin de procédure de “réparation locale”. Cela a deux avantages: la preuve de correction de l’algorithme est plus simple à établir, et d’un point de vue pratique, l’implantation est plus facile et plus efficace.