Séminaire du 15 mars 04, Damien Stehlé.

L'algorithme récursif binaire de calcul du pgcd

Les algorithmes naifs 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\log^2n\log\log n)$, cette borne a été prouvée par Schönhage), qui repose sur la multiplication rapide d'entiers, à base de FFT. Cet algorithme est une variante récursive de l'algorithme d'Euclide. La preuve de correction de cet algorithme est difficile à établir en raison d'une routine de ``réparation locale" des quotients calculés. Cela rend l'implantation pénible, difficile à certifier et souvent inefficace pour des nombres de taille raisonnable. Nous présenterons ici un algorithme récursif basé non pas sur la division Euclidienne classique mais sur une nouvelle 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 simple. (Travail commun avec Paul Zimmermann, Loria/Inria Lorraine)