Algorithme GCD de Lehmer - Lehmer's GCD algorithm

L'algorithme GCD de Lehmer , nommé d'après Derrick Henry Lehmer , est un algorithme GCD rapide , une amélioration par rapport à l' algorithme euclidien plus simple mais plus lent . Il est principalement utilisé pour les grands entiers qui ont une représentation sous forme de chaîne de chiffres par rapport à une base de système numérique choisie , par exemple β = 1000 ou β = 2 ³² .

Algorithme

Lehmer a noté que la plupart des quotients de chaque étape de la partie division de l'algorithme standard sont petits. (Par exemple, Knuth a observé que les quotients 1, 2 et 3 représentent 67,7% de tous les quotients.) Ces petits quotients peuvent être identifiés à partir de seulement quelques chiffres de tête. Ainsi, l'algorithme commence par séparer ces premiers chiffres et calculer la séquence des quotients tant qu'elle est correcte.

Disons que nous voulons obtenir le GCD des deux entiers a et b . Soit a ≥ b .

• Si b ne contient qu'un seul chiffre (dans la base choisie , disons β = 1000 ou β = 2 ³² ), utilisez une autre méthode, telle que l' algorithme euclidien , pour obtenir le résultat.
• Si a et b diffèrent par la longueur des chiffres, effectuez une division de sorte que a et b soient égaux en longueur, avec une longueur égale à m .
• Boucle externe: Itérer jusqu'à ce que l'un de a ou b soit égal à zéro:
  • Diminuez m par un. Soit x le premier chiffre (le plus significatif) de a , x = a div β ^m et y le premier chiffre de b , y = b div β ^m .
  • Initialiser une matrice 2 par 3

  ${\ displaystyle \ textstyle {\ begin {bmatrix} A & B & x \\ C & D & y \ end {bmatrix}}}$à une matrice d'identité étendue ${\ displaystyle \ textstyle {\ begin {bmatrix} 1 & 0 & x \\ 0 & 1 & y \ end {bmatrix}},}$

  et exécutez l'algorithme euclidien simultanément sur les paires ( x + A , y + C ) et ( x + B , y + D ), jusqu'à ce que les quotients diffèrent. Autrement dit, itérer comme une boucle interne :

  • Calculez les quotients w ₁ des divisions longues de ( x + A ) par ( y + C ) et w ₂ de ( x + B ) par ( y + D ) respectivement. Soit également w le quotient (non calculé) de la division longue courante dans la chaîne des divisions longues de l'algorithme euclidien.

  • • Si w ₁ ≠ w ₂ , sortez de l'itération interne. Sinon, réglez w sur w ₁ (ou w ₂ ).
    • Remplacer la matrice actuelle

    ${\ displaystyle \ textstyle {\ begin {bmatrix} A & B & x \\ C & D & y \ end {bmatrix}}}$

    avec le produit matrice

    ${\ displaystyle \ textstyle {\ begin {bmatrix} 0 & 1 \\ 1 & -w \ end {bmatrix}} \ cdot {\ begin {bmatrix} A & B & x \\ C & D & y \ end {bmatrix}} = {\ begin {bmatrix} C & D & y \ \ A-wC & B-wD & x-wy \ end {bmatrix}}}$

    selon la formulation matricielle de l'algorithme euclidien étendu.

    • Si B ≠ 0, va au début de la boucle interne.
  • Si B = 0, nous sommes dans une impasse ; exécutez une étape normale de l'algorithme euclidien avec a et b , et redémarrez la boucle externe.
  • Réglez a sur aA + bB et b sur Ca + Db (à nouveau simultanément). Ceci applique les étapes de l'algorithme euclidien qui ont été effectuées sur les premiers chiffres sous forme compressée aux longs entiers a et b . Si b ≠ 0 va au début de la boucle externe.

Les références

• Kapil Paranjape , l'algorithme de Lehmer