Complexité du algorithme d'Euclide

• A chaque itération on calcule un nombre constant des opérations arithmétiques que coûtent  au pire.

Pourquoi????

•  Combien de fois ???

 
•  Par le théorème de Lamé: soit s le nombre des itérations, alors  , (où f sont des nombres de Fibonacci).

 
•  Mais

 

 


 

• Donc s est  . Pourquoi ????

 

 

• Et pour RSA le calcul de l'inverse est au pire 


(En fait un calcul plus précis montre que la complexité est