Algorithme d'Euclide

[nadia]

Bonjour,
Je n'arrive pas à montrer le résultat suivant, je vous prie de m'aider à le faire:
le nombre d'itérations dans l'algorithme d'Euclide pour déterminer le PGCD de deux nombres de longueur n -bit est au plus 2n. merci d'avance.

[pascal16]

je pense qu'il faut se baser sur 2 cas.

à une étape donnée, soit p la position du bit de poids le plus fort des deux nombres
-> si le bits de poids le plus fort est <p pour le plus petit, le reste aura forcément un bit de poids le plus fort <p, soit p-1 max et à l'étape suivant, on a perdu 1 rang pour p
-> si le bits de poids le plus fort ont la même position p, on se retrouve dans le premier cas à l'étape suivante.

dans le pire des cas, on retombe toujours sur le cas 2 qui demande 2 étapes pour passer de p à p-1 soit 2n étapes max