Next:
Résultats utiles
Up:
No Title
Previous:
Exemple
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