Résumé de l'exposé :
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 log^2 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 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 facile et plus efficace.