Algorithme d’Euclide : le calcul antique au cœur des codes

Intervenant 10:00

Bienvenue à toutes et à tous dans le podcast du magazine Tangente pour une nouvelle plongée fascinante.

Intervenant 20:05

Bonjour et merci de me recevoir pour cette exploration.

Intervenant 10:09

Je suis vraiment ravie de t'avoir avec nous aujourd'hui parce qu'on va entrer dans le vif du sujet tout de suite. Chaque fois qu'on sort un smartphone pour acheter un billet de concert ou qu'on entre un numéro de carte bancaire sur un site, la sécurité absolue de cette transaction dépend d'une logique mathématique imaginée par un savant grec en tunique il y a plus de 2300 ans.

Intervenant 20:32

C'est un contraste qui est totalement saisissant, n'est-ce pas ? On a l'habitude d'associer la cybersécurité, les algorithmes, à des choses très froides, des serveurs qui clignotent, la Silicon Valley, bref, la modernité absolue.

Intervenant 10:46

Ouais, c'est clair.

Intervenant 20:47

Mais en fait, la clé de voûte de tout notre système numérique moderne, elle repose sur un texte de l'Antiquité.

Intervenant 10:54

Mais c'est une idée complètement vertigineuse. Et c'est exactement ce qui nous réunit aujourd'hui. Pour guider notre audience, on s'appuie sur un texte exceptionnel tiré de l'article Algorithme d’Euclide, etc. Un article qui a d'ailleurs été primé lors du prix du meilleur article du Club Tangente en 2020.

Intervenant 21:10

Un excellent article, oui.

Intervenant 11:12

L'objectif de notre exploration aujourd'hui, c'est de comprendre comment cette idée millénaire fait littéralement tourner notre monde d'aujourd'hui. Mais avant de plonger dans la technique, il faut vraiment qu'on crève un abcès historique. Ah, je sens qu'on va parler du titre. Exactement. Le titre même de cet article est l'expression « l'algorithme d'Euclide ». En fait, ça cache une énorme supercherie temporelle, non ?

Intervenant 21:34

Totalement. C'est un anachronisme massif. Historiquement parlant, accoler le mot « algorithme » au nom d'Euclide, ça n'a aucun sens. Pourquoi ? Euclide a vécu à Alexandrie au IIIe siècle avant notre ère. Or, le terme « algorithme », lui, il dérive du nom du grand mathématicien persan Al-Khwarizmi.

Intervenant 11:55

Qui vivait beaucoup plus tard, c'est ça ?

Intervenant 21:56

Voilà, au IXe siècle de notre ère. Donc on parle de plus de mille ans d'écart entre l'auteur de la méthode et le mot qu'on utilise pour la décrire.

Intervenant 12:04

Ah ouais, quand même. Bon, décortiquons tout ça. En gros, dire l'algorithme d'Euclide, c'est un peu comme si on qualifiait un char romain antique de voiture de sport hybride.

Intervenant 22:16

C'est une très bonne métaphore, ça.

Intervenant 12:17

On comprend l'idée de fond, tu vois. On veut dire que c'est un véhicule hyper rapide, mais l'étiquette est juste totalement hors contexte.

Intervenant 22:24

Ouais, c'est exactement ça. Si on voulait être, disons, historiquement irréprochable, il faudrait s'en tenir à la définition stricte du site BIMMATATRI qui dit, je cite de mémoire, « une succession de règles très précises à appliquer en vue de résoudre un problème ».

Intervenant 12:40

C'est tout de suite moins fluide à placer dans une conversation mondaine, ça.

Intervenant 22:43

C'est sûr. Donc par pure commodité, on accepte ce raccourci de langage. Mais ce qui est remarquable au fond, c'est que la mécanique de ce char romain, pour reprendre ton analogie, reste l'une des plus robustes de toute l'histoire des sciences.

Intervenant 12:55

Alors justement, soulevons le capot de ce fameux char. De quoi on parle exactement ? L'article nous emmène dans le livre VII d'un monument des mathématiques, les éléments d'Euclide.

Intervenant 23:05

Et ce livre 7, c'est une merveille d'organisation logique. Il ne ressemble pas du tout à un manuel de calcul moderne avec des petites formules.

Intervenant 13:12

Comment ça se présente alors ?

Intervenant 23:15

Eh bien, il s'ouvre sur des fondations philosophiques et structurelles. T'as des définitions très strictes. Qu'est-ce qu'une unité ? Qu'est-ce qu'un nombre ? Qu'est-ce que la notion de nombre premier entre eux ?

Intervenant 13:26

D'accord, il pose les bases de l'univers avant de jouer dedans.

Intervenant 23:29

C'est tout à fait ça. Et tout en haut de cet édifice intellectuel, on trouve le théorème 7.1 qui décrit ce fameux procédé. Et tu t'en doutes, à l'époque, les Grecs ne parlaient pas d'algorithme. Ils utilisaient un terme beaucoup plus poétique et un peu complexe, l'antiphérèse.

Intervenant 13:44

L'anti quoi ?

Intervenant 23:45

L'antiphérèse. Waouh, on dirait presque le nom d'une maladie tropicale.

Intervenant 13:49

Plus sérieusement, c'est ce qu'on appelle l'algorithme des soustractions, c'est bien ça ?

Intervenant 23:53

Ouais, l'algorithme des soustractions successives.

Intervenant 13:56

Calculer le PGCD, le plus grand commun diviseur au collège, on fait des divisions. On prend un grand nombre, on le divise par un plus petit, on regarde le reste et on recommence. Pourquoi Euclide, lui, s'encombrait de soustractions à la chaîne ? Ça a l'air atrocement long et fastidieux.

Intervenant 24:13

Et ce qui est fascinant ici, c'est de comprendre la mentalité géométrique des Grecs.

Intervenant 14:17

C'est-à-dire ?

Intervenant 24:18

Bah pour eux, un nombre, c'est pas juste un concept abstrait, un symbole écrit sur un bout de papier. Un nombre, c'est une longueur. C'est un segment de droite concret.

Intervenant 14:26

Ah, je vois. Alors si je pousse la logique, l'antiférèse, c'est un peu comme si disons que j'ai un grand terrain rectangulaire de 16 mètres sur 6 mètres et je veux le découper en parcelles carrées parfaites, les plus grandes possibles, sans qu'il ne reste le moindre centimètre carré de terre à la fin.

Intervenant 24:45

C'est l'illustration parfaite. Alors comment tu t'y prendrais avec la méthode d'Euclide, cette fameuse soustraction ?

Intervenant 14:52

Dans un rectangle de 16 par 6, je vais essayer de visualiser. Je peux d'abord découper deux grands carrés de 6 par 6.

Intervenant 25:00

Très bien, ça fait 12 mètres utilisés sur les 16.

Intervenant 15:02

Voilà, donc il me reste un petit bout de terrain de 4 mètres sur 6. Là-dedans, je découpe un carré de 4 par 4.

Intervenant 25:10

Il te reste donc ?

Intervenant 15:11

Il me reste un petit rectangle de 4 par

Intervenant 25:13

2.

Intervenant 15:13

Et enfin, dans ce 4 par 2, je coupe exactement deux carrés parfaits de 2 par 2. Et paf, il ne reste plus rien. Donc, mon unité de mesure commune, mon PGCD, c'est 2.

Intervenant 25:24

Exactement. Et là, tu viens de décrire étape par étape la méthode originale d'Euclide.

Intervenant 15:29

Sans faire une seule division.

Intervenant 25:31

Juste en coupant des morceaux. C'est ça. Tu as retiré la petite dimension de la grande, encore et encore, jusqu'à épuisement. C'est purement visuel, très géométrique. Et d'ailleurs, il y a une autre nuance historique capitale que l'article souligne, en s'appuyant sur des éditions du XVIIe siècle.

Intervenant 15:47

Laquelle ?

Intervenant 25:48

Aujourd'hui, on lance ce calcul spécifiquement pour trouver ce nombre final, ce PGCD de 2 dans ton exemple. Mais pour Euclide, le calcul de ce PGCD, il n'arrive qu'à la deuxième proposition.

Intervenant 15:59

Ah bon ? Mais c'était quoi son but premier alors ?

Intervenant 26:01

Son objectif premier dans la proposition 1, c'était de vérifier si deux nombres étaient premiers entre eux.

Intervenant 16:05

Attends, donc c'est vérifier si, à la fin de notre découpage de terrain de tout à l'heure, on se retrouve bloqué avec des tout petits carrés de 1 mètre sur 1 mètre ?

Intervenant 26:14

C'est tout à fait ça. Si la seule unité commune à la fin c'est 1, ça veut dire que tes nombres de départ n'ont aucun autre diviseur en commun. Ils sont premiers entre eux. Euclide cherchait d'abord à caractériser la relation intime entre deux grandeurs, leur incommensurabilité éventuelle.