Cryptographie · Interactif

Algorithme d'Euclide pas à pas

Saisis deux entiers et déroule l'algorithme d'Euclide division par division. Compteur d'étapes, presets Fibonacci pour comparer avec les pires cas.

Tester :
Saisis deux entiers et clique sur « Calculer le PGCD », ou choisis une paire prédéfinie ci-dessus.
    L'algorithme d'Euclide remplace le couple (a, b) par (b, r) à chaque étape, où r est le reste de la division euclidienne. L'algorithme s'arrête quand le reste devient nul. Le PGCD est alors le diviseur de la dernière division.
    Voir dans son contexte Le théorème de Lamé : Fibonacci, le PGCD, et la naissance de la complexité algorithmique