Pourquoi l'algorithme d'Euclide, vieux de 2 300 ans, est-il toujours aussi rapide ?

Pourquoi cette question : un modèle d'introduction

Le jury attend que vous expliquiez pourquoi vous avez choisi la question. Inspirez-vous de ce modèle, mais racontez votre propre parcours.

J'ai appris l'algorithme d'Euclide au collège sans me demander s'il était efficace. En NSI, en le programmant, j'ai constaté qu'il trouvait instantanément le PGCD de nombres de cent chiffres. Je me suis demandé combien d'étapes il pouvait demander au pire, et j'ai été surpris de retrouver la suite de Fibonacci dans la réponse.

L'enjeu et les notions du programme

Majorer le nombre d'étapes d'un algorithme à l'aide d'une suite et du logarithme.

Le plan de l'exposé en 9,5 min

1. 1. Introduction

   1 min

   L'algorithme d'Euclide calcule le PGCD de deux entiers en remplaçant $(a,b)$(a,b) par $(b,r)$(b,r), où $r$r est le reste de la division de $a$a par $b$b, jusqu'à obtenir un reste nul. Problématique : combien d'étapes faut-il au maximum ?

2. 2. Mathématiques : terminaison et pire cas

   4 min

   Exemple : $1071=2\times 462+147$1071=2×462+147, $462=3\times 147+21$462=3×147+21, $147=7\times 21+0$147=7×21+0. Le PGCD est 21, en 3 divisions.

   Terminaison : les restes sont des entiers positifs strictement décroissants ($0\le r<b$0≤ r<b) : la suite ne peut pas descendre indéfiniment.

   Pire cas : on cherche les plus petits nombres qui demandent $k$k étapes. Si chaque quotient vaut 1, on remonte $a=b+r$a=b+r : c'est la relation $F_{n+1}=F_n+F_{n-1}$Fₙ₊₁=Fₙ+Fₙ₋₁ de Fibonacci. Avec $89$89 et $55$55 : $89=55+34$89=55+34, $55=34+21$55=34+21, …, jusqu'à $2=2\times 1+0$2=2×1+0 : 9 divisions, le maximum pour des nombres de cette taille.

   La suite de Fibonacci croît comme ${\phi }^n$φⁿ avec $\phi =\frac{1+\sqrt{5}}{2}\approx 1,618$φ=(1+sqrt5)/2≈1,618. Le nombre d'étapes est donc au plus de l'ordre de ${\log }_{\phi }b=\frac{\ln b}{\ln \phi }$log_φ b=(ln b)/lnφ. Comme ${\log }_{\phi }10\approx 4,8$log_φ10≈4,8, on obtient le théorème de Lamé : au plus environ 5 fois le nombre de chiffres de $b$b.

3. 3. NSI : programme et coût

   3 min

   En Python : tant que $b\ne 0$b≠0, on remplace $a,b$a,b par $b,a\%b$b,a % b. Le variant de boucle est $b$b, entier positif qui décroît strictement : il prouve la terminaison.

   Pour deux nombres de 100 chiffres, au plus environ 480 divisions : instantané. C'est pour cela qu'il est utilisé en cryptographie, par exemple pour calculer la clé privée de RSA avec sa version étendue. On le compare à la méthode « décomposer en facteurs premiers puis prendre les facteurs communs », qui exige de factoriser : impossible pour de grands nombres.

4. 4. Conclusion

   1,5 min

   L'algorithme d'Euclide est rapide parce que les restes décroissent au moins aussi vite que la suite de Fibonacci à l'envers : le nombre d'étapes est logarithmique. Un algorithme antique reste un outil moderne. J'ouvre sur l'algorithme d'Euclide étendu, qui donne les coefficients de Bézout.

Ce que j'écris au tableau

Pas de calculatrice ni de support numérique : un calcul clé écrit au tableau rend l'exposé concret et montre la solidité des connaissances.

Conclusion : la réponse à la question

Les questions probables du jury

Pendant les 10 minutesd'échange, le jury vous fait préciser et approfondir, sur tout le programme de vos spécialités en lien avec la question.

Les pièges qui coûtent des points

• Confondre nombre d'étapes et valeur du PGCD.
• Oublier de justifier la terminaison.
• Croire que le pire cas est celui de deux grands nombres premiers.

Revoir les notions

• Nombres et calculs (Seconde) →
• Suites : récurrence et limites (Terminale spé maths) →

Autres questions : algorithmes et complexité

• Pourquoi trier un million de nombres peut-il prendre dix minutes ou un centième de seconde selon l'algorithme ?
• Pourquoi couper un problème en deux permet-il de le résoudre beaucoup plus vite ?
• Peut-on inventer un algorithme de tri encore plus rapide, ou existe-t-il une limite infranchissable ?
• Un ordinateur mille fois plus rapide permet-il de résoudre des problèmes mille fois plus grands ?

Toutes les questions maths-nsi →