Retour à l'index du GREYC

Séminaire Algorithmique

Site du CNRS

Séminaire Algorithmique

Le séminaire a lieu le mardi à 11 h 45 (sauf modification exceptionnelle), au campus Côte de Nacre, bâtiment Sciences 3, salle S3 351, 3ème étage.

Résumé du séminaire du Mardi 27 Janvier 2004

L'algorithme binaire recursif de calcul de pgcd

par 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.

GREYC
Campus Côte de Nacre, boulevard du Maréchal Juin
BP 5186
14032 Caen Cedex
FAX : +33 (0)2 31 56 73 30
http://www.greyc.fr