Cryptographie · Interactif

Découpage géométrique d'Euclide

Visualisation géométrique de l'algorithme d'Euclide comme découpage de carrés successifs. Pour les paires Fibonacci, la spirale de Fibonacci apparaît : c'est le pire cas du théorème de Lamé.

Rectangle
89 × 55
Étapes Euclide
9
Carrés total
10
PGCD
1

Paire de Fibonacci consécutifs : tous les quotients valent 1, sauf le dernier. La spirale qui apparaît est la signature du pire cas de l'algorithme.

À chaque étape, on découpe le plus grand carré possible dans le rectangle restant. Pour les paires de Fibonacci consécutifs, chaque étape ne consomme qu'un seul carré, ce qui maximise le nombre d'étapes. Pour les autres paires, certaines étapes consomment plusieurs carrés d'un coup, et le total est plus court. C'est cette différence qui fait que Fibonacci est le pire cas.
Voir dans son contexte Le théorème de Lamé : Fibonacci, le PGCD, et la naissance de la complexité algorithmique