23 soldats : l’énigme du théorème des restes chinois

Intervenant 10:00

Bienvenue dans le podcast du magazine Tangente. Je suis ravi de vous retrouver aujourd'hui pour une plongée disons assez vertigineuse.

Intervenant 20:08

Ouais, vertigineuse, c'est le mot. Je suis ravie d'être là pour décortiquer ça avec toi.

Intervenant 10:12

Super. Alors, si on disait à ceux qui nous écoutent que la sécurité totalement inviolable de leurs comptes bancaires ou même le chiffrement de leurs messages privés...

Intervenant 20:22

Les fameux messages de bout en bout, là. Voilà,

Intervenant 10:23

exactement. Si on disait que tout ça repose en grande partie sur un obscur problème de logistique militaire inventé en Chine il y a plus de 1500 ans, ça semblerait complètement absurde, non ?

Intervenant 20:36

Totalement absurde. On a souvent tendance à imaginer les mathématiques modernes, et surtout celles de la cryptographie, comme un truc né dans un labo immaculé, tu vois.

Intervenant 10:45

Avec des serveurs qui clignotent

Intervenant 20:47

dans le noir, c'est ça ? Ouais. Il y a cette attente d'une technologie qui serait purement contemporaine, presque abstraite dès sa création. On voit la sécurisation des données comme une science née avec l'informatique, quoi. Quelque chose de complètement déconnecté du monde physique.

Intervenant 11:02

Sauf que la réalité est bien différente. Et c'est tout l'objet de notre exploration d'aujourd'hui. Notre décryptage du jour s'attaque à ce qu'on appelle le théorème des restes chinois.

Intervenant 21:11

Un gros morceau.

Intervenant 11:13

Ah oui, un très gros morceau. Mais pour comprendre comment on en est arrivé à sécuriser des milliards de transactions, on ne va pas commencer par des équations indigestes.

Intervenant 21:21

Heureusement pour Lou, ouais !

Intervenant 11:22

Mais oui, il faut se salir un peu les bottes. On va faire un bond dans le temps. Direction la Chine, entre le IIIe et le Ve siècle de notre ère, juste après la dynastie Han. On se retrouve sur un champ de bataille.

Intervenant 21:34

Et le personnage central de cette époque, du moins pour notre décryptage, c'est un certain Sun Zi. C'est un mathématicien et astronome.

Intervenant 11:43

Attention à ne pas confondre avec le célèbre stratège.

Intervenant 21:47

Oui, Sun Tzu, l'auteur de l'art de la guerre. Ce n'est pas la même personne. Notre savant, Sun Tzu, a laissé derrière lui une énigme. Et, sous ses airs de petit casse-tête de rien du tout, ça cache un gouffre arithmétique assez incroyable.

Intervenant 12:02

Alors, l'énigme, elle met en scène un général. Le général Han Xing. Ce type doit compter ses troupes après une bataille. Mais il ne le fait pas un par un parce que ce serait beaucoup trop long.

Intervenant 22:14

Surtout avec une armée entière,

Intervenant 12:15

oui. C'est clair. Du coup, l’énigme dit la chose suivante. Quand le général range ses soldats en rang de trois, il lui reste deux soldats sur le côté.

Intervenant 22:24

OK.

Intervenant 12:25

Quand il les regroupe par cinq, il lui en reste trois. Et quand il fait des rangs de sept, il lui en reste deux. La question est super simple. Combien de soldats il y a dans cette armée ?

Intervenant 22:37

Et en fait, derrière cette petite comptabilité de terrain, il y a un problème super profond de divisibilité. L'objectif, c'est vraiment de débusquer un nombre précis, sans rien connaître de ce nombre, à part ces fameux restes, les restes des divisions successives par 3, par 5 et par 7.

Intervenant 12:56

Bon, décortiquons un peu tout ça. Face à ce genre de problème, le premier réflexe humain, je pense, c'est la force brute. C'est un peu comme...

Intervenant 23:03

Essayer toutes les solutions, quoi.

Intervenant 13:04

Voilà. C'est comme se retrouver devant un cadenas à code, un cadenas de vélo dont on a perdu la combinaison. On teste 001, 002... Et on y passe

Intervenant 23:13

la journée.

Intervenant 13:13

Exactement. On pourrait compter un par un jusqu'à trouver le bon effectif. Mais la source de notre sujet montre qu'il y a une astuce logique immédiate. Si on trouve une solution à ce problème, on détient en fait la clé pour une infinité d'autres solutions.

Intervenant 23:27

Et pour comprendre pourquoi, il faut juste regarder nos trois diviseurs. On avait 3, 5 et 7. Si on les multiplie entre eux, on obtient 105. Ça, c'est leur multiple commun.

Intervenant 13:37

Ok, je te suis.

Intervenant 23:38

Ben, imaginons qu'on ait trouvé une armée d'une certaine taille, qui respecte toutes les conditions du général. Si on fait venir 105 soldats supplémentaires, ces nouveaux arrivants, ils pourront se ranger en colonnes parfaites de 3, de 5 et de 7. Et

Intervenant 13:52

s'en laisser le monde reste, du coup.

Intervenant 23:53

Exactement, zéro reste, donc ils ne viennent absolument pas perturber les petits groupes initiaux.

Intervenant 13:58

Ah, je vois. En gros, mathématiquement parlant, ça garantit que la plus petite solution possible, elle se trouve obligatoirement entre 1 et 105. C'est

Intervenant 24:08

ça. Le champ de recherche est quand même drastiquement réduit. On passe de l'infini à juste 105 possibilités.

Intervenant 14:15

Bon, même réduit à 105, si on est sur le terrain, tester les nombres un par un sur un parchemin, ça reste super fastidieux. Faut trouver une méthode plus élégante. On pourrait envisager de faire des listes croisées, non ?

Intervenant 24:26

C'est ce qu'on appelle la méthode des suites, ouais. Au jour de tester à l'aveugle, on écrit les possibilités pour chaque condition. Pour la première règle, un reste de 2 quand on divise par 3, on écrit tous les effectifs possibles.

Intervenant 14:39

Donc 2, puis 5, 8, 11, 14, 17, 20, 23. On avance juste par bon de 3 en fait.

Intervenant 24:47

Voilà. Et on applique la même logique à la deuxième règle. Un reste de 3 quand on divise par 5. La liste, ça va être 3, 8, 13, 18, 23.