Des codes et des grilles

Drapeau vert : Cet article ne demande aucune connaissance mathématique particulière


La dernière fois, nous avions parlé de méthodes de chiffrement que l’on appelle « par substitution » : une lettre était remplacée par une autre dans l’alphabet. Ces méthodes, aussi ludiques soient-elles, s’avéraient finalement peu fiables.

Pour renforcer la sécurité de la communication, il est possible de transposer les lettres, d’en inverser l’ordre. Aussi, on peut penser à les dissimuler au milieu d’un message bien plus grand, à condition d’avoir une méthode simple pour notre destinataire de trouver les lettres utiles.

Voici quelques exemples simples de ces procédés

La scytale

Utilisée par les spartiates, la scytale est un bâton autour duquel on enroule de manière régulière une bande de papier avant d’écrire un message dessus. Ainsi, en déroulant la bande, l’ordre des lettres du message d’origine est chamboulé.

Une scytale tant artisanale que subliminale. En déroulant le message ABONNEZVOUSAUBLOG!, on obtient ANOUO BEUBG OZSL! NVA

Pour décoder le message ainsi obtenu, il suffit d’enrouler de nouveau la bande autour d’un bâton similaire, rien d’extraordinaire.

Conceptuellement, ce procédé revient à écrire le message selon les lignes d’un tableau qui comporte autant de colonnes que de lettres nécessaires pour faire un tour de la scytale. Dans l’exemple plus haut, je pouvais placer 4 lettres sur une rangée, on utilise donc un tableau à 4 colonnes.

A B O N
N E Z V
O U S A
U B L _
O G !

Vous apercevez un caractère manquant sur la quatrième ligne :  c’est tout simplement parce que je manquais de papier pour l’écrire sur ma bande ! Pas de panique, le message reste déchiffrable. Le message codé correspond à la suite de lettres obtenue en lisant colonne par colonne.

Le problème, c’est que le nombre de combinaison à tester pour déchiffrer le message est très réduit : pour celui qui intercepte le message, il suffit de lire toutes les deux lettres, ou toutes les trois lettres, ou toutes les quatre et ainsi de suite pour arriver au bon résultat. Bref, il n’y a pas vraiment besoin de posséder une exacte réplique du bâton d’origine pour décrypter le message…

Il se peut que la scytale ait également été utilisée comme une méthode d’identification plutôt que de codage, une sorte de mot de passe avant l’heure si l’on veut.

Ainsi, pour être certain de l’identité de l’expéditeur d’un message, il fallait que celui-ci ait rédigé son message à l’aide d’une scytale d’une certaine forme et d’un certain diamètre. Si, en enroulant le message sur la scytale, celui-ci produisait un texte incompréhensible, alors le message était rejeté. Ce procédé aurait permis d’empêcher les espions ennemis de diffuser de fausses informations au sein d’une armée.

La grille de Cardan

Autre époque, autre méthode. La grille de Cardan, du nom du mathématicien Jérôme Cardan, a pour but de masquer un message secret au sein d’un message bien plus long. Pour cela, on utilise une grille à trou que l’on pose sur une feuille de papier et on y inscrit le message à dissimuler. Ensuite, en retirant le cache, on complète le reste de la feuille. Le destinataire n’a plus qu’à utiliser un cache identique pour voir apparaître le message d’origine.

Naturellement, il est possible de compléter le message avec des lettres prises au hasard, mais le but de la manoeuvre ici est de paraître totalement innocent : un message inintelligible attirerait à coup sûr l’attention. Il valait donc mieux compléter intelligemment, en faisant mine de transmettre un message anodin.

Grille de Cardan

Un message secret apparaît lorsque l’on utilise la grille.

La grille de Cardan n’est d’ailleurs pas une méthode de cryptographie à proprement parler. Généralement, on remarque immédiatement qu’un message est crypté puisqu’il est inintelligible, ce qui n’était pas le cas ici. On parlera plutôt de stéganographie, l’art de dissimuler le message.

Toute la difficulté était d’ailleurs ici : à une époque où l’ordinateur n’existait pas, il fallait garder une écriture régulière, ne pas laisser de grands espaces ou trop resserrer les caractères, mais aussi posséder un vocabulaire fourni pour pouvoir compléter le message.

Le problème de cette méthode se trouvait également dans la transmission et la conservation de la grille de décodage : si celle-ci était volé ou perdue, c’est toute la communication qui était rompue !

Les grilles du colonel Fleissner

Restons das les grilles, mais d’un autre genre, puisque nous allons les faire tourner. Ces grilles tournantes ont été popularisées par le colonel autrichien Fleissner dans son ouvrage Handbuch der Kryptographie. Fleissner remplit cette fois une feuille de papier divisée en 36 petits carreaux, ordonnée en carré de 6 carreaux de côté.

La grille, maintenant, est également un carré de 6 carreaux de côté dans laquelle on a toutefois retiré 9 d’entre eux. Mettons que l’on souhaite crypter notre message favori : LESMATHEMATIQUESCESTFANTASTIQUE.

  • D’abord, on place la grille sur la feuille et on complète les trous des 9 premières lettres, ici LESMATHEM.
  • On tourne ensuite la grille d’un quart de tour, dans un sens ou dans l’autre. De cette manière, on masque les lettres déjà inscrites et on révèle 9 nouveaux espaces vides.
  • On continue alors le remplissage de la feuille de papier en utilisant les trous de la grille.
  • On répète le procédé jusqu’à remplir nos 36 cases. Si le message fait plus de 36 lettres, on utilise une autre grille. S’il en fait moins, on complète avec des lettres aléatoires.

Voici une animation de cette méthode :

On remplit la grille case par case, puis on la fait tourner d’un quart de tour et on recommence.

Avec cette grille, le message codé est IASQLTTEIQUSMFEAAUPNTEHTASSESLETCMA. Avec une autre grille, il serait bien sûr différent.

Pour déchiffrer le message, on utilise la même grille que l’on pose sur la feuille, puis on la fait tourner comme pour chiffrer.

La sécurité de cette méthode dépend donc du nombre de grilles qu’il est possible de fabriquer. D’abord, il convient de remarquer qu’il ne faut pas prendre 9 trous absolument au hasard. En effet, si l’on regarde le carreau tout en haut à droite, celui-ci se retrouve en haut à gauche, puis en bas à gauche et enfin, en haut à droite à mesure que nous effectuons les quarts de tours.

Il ne faut donc trouer une et une seule case parmi celles-ci : ne pas en trouver rendrait ces cases inatteignables, en trouer plusieurs demanderait d’écrire plusieurs lettres sur une même case. En observant plus en détails notre grille, on en déduit qu’il faut percer un et un seul trou de chaque couleur sur la grille suivante :

En voilà des couleurs… Pour une grille de Fleissner valable, il faut percer un et un seul trou pour chaque couleur / numéro.

Puisque nous avons 9 couleurs / numéros et que pour chacun deux il y a 4 possibilités de trous, cela donne 49 possibilités, soit 262144 grilles différentes. Alors évidemment, parmi elles il y en a de trop simples comme la grille qui consistes à enlever toute la partie supérieure droite, mais cela fait un nombre raisonnable quand on n’a pas d’ordinateur à portée de main.

D’ailleurs, il est possible d’utiliser des grilles plus grandes, toujours en trouant un quart des positions à chaque fois. En utilisant non pas 6 mais 8 carreaux de côté, il y aura alors 4294967296 possibilités de grilles.

Pour casser un tel chiffrage, il faut alors utiliser une attaque par mot probable : on suppose que le texte contient un mot et l’on essaye de recomposer la grille – ou au moins de réduire les possibilités par ce biais.

Naturellement, il est possible, comme mentionné au début, de combiner ces approches au chiffrement par substitution. Ainsi pourrez-vous espérer communiquer sans vous faire prendre ?

Pour compléter

Publié dans Cryptographie | Tagué , , , , | Laisser un commentaire

Vos papiers, s’il vous plait !

Drapeau jaune : Cet article demande quelques connaissances mathématiques de base et un peu d’abstraction pour être entièrement saisi.


L’une des grandes questions de votre enfance, outre la fabrication des bébés, aura peut-être concerné les dimensions de vos feuilles de papier et de vos cahiers à l’école : le fameux format A4 mesure ainsi 21 cm de large pour 29,7 cm de long.

Alors, pourquoi ce 29,7 précisément ? Pourquoi ne pas arrondir à 21 x 30, ou même 20 x 30, histoire d’avoir de jolis nombres ?

L’explication cachée derrière cette fantaisie est -évidemment – d’ordre mathématique.

Plier et replier

S’il existe un  format A4, vous vous doutez bien qu’il existe un format A3, A2, A1 et également un format A0. A vrai dire, pour obtenir une feuille au format A3,il suffit de mettre côte a côté deux feuilles A4 en les collant suivant la longueur.

Inversement, en pliant une feuille A3 en deux, suivant sa longueur, on obtient une feuille de format A4.

Formats papier

Les différents formats de papier s’obtiennent par pliages successifs.

Ainsi, le format A1 est obtenu par un pliage d’une feuille de format A0, le A2 par deux pliages, le A3 par 3 pliages et ainsi de suite. Et puisqu’à chaque fois, la surface est divisée par deux, cela signifie que les surfaces des feuilles A1, A2, A3 sont respectivement 2, 4 et 8 fois plus petites que la surface du format A0.

Toutefois, cela ne nous en dit pas plus sur les longueurs des côtés de nos feuilles de papier. Simplement, il suffit de déterminer les mesures du format A0 pour que les mesures des formats suivants en découle.

Format A. On passe du A0 au A1 eu découpant en deux parts égales selon la longueur.

En fait, il y a deux autres propriétés que l’on souhaite avoir avec nos feuilles de papiers.

D’abord, on souhaite garder les mêmes proportions, la même valeur pour le rapport entre la longueur et la largeur. En gros, on veut que toutes nos feuilles conservent la même forme.

Prenons alors notre feuille au format A0, et notons sa longueur L et sa largeur l. En la pliant en deux selon la longueur, on obtient une feuille au format A1. La longueur de cette nouvelle feuille vaut l et sa largeur vaut la moitié de la longueur de notre feuille de départ, soit L/2.

Or, nous voulons que les formats A0 et A1 aient les mêmes proportions, ce qui se traduit par l’égalité

\frac{L}{l} = \frac{l}{L / 2}

En modifiant légèrement cette égalité, on obtient \left(\frac{L}{l}\right)^{2} = 2 soit L/l = √2, soit environ 1.414.

Ensuite, il suffit de fixer la surface d’une feuille au format A0 pour en déduire toutes nos mesures. En l’occurrence, une feuille A0 recouvre 1m², ce qui nous donne, en exprimant la longueur L et la largeur l en mètres, le système d’équations suivant :

  • L x l = 1
  • L / l =√2

On en vient aux valeurs L = \sqrt{\sqrt{2}} et l = 1 / \sqrt{\sqrt{2}}. Malheureusement, ces valeurs sont irrationnelles. Pas le choix, il faut les arrondir. Ainsi, la longueur d’une feuille A0 est d’environ 1.189 m, soit 118,9 cm tandis que sa largeur est de 0.841 m soit 84,1 cm.

De proche en proche on calcule alors les longueurs et largeurs des formats A0, A1, A2 et ainsi de suite…

Format Longueur (cm) Largeur (cm) Surface voulue (cm²) Surface réelle (cm²)
A0 118,9 84,1 10000 9999.49
A1 84,1 59.4 5000 4995.54
A2 59,4 42,0 2500 2494,80
A3 42,0 29,7 1250 1247,40
A4 29,7 21,0 625 623,70
A5 21,0 14,8 312,5 310.80
A6 14,8 10,5 156,25 155,4

Nous retrouvons bien 21 x 29,7 pour la feuille au format A4, et nous pouvons continuer ainsi, de plus en plus petit.

D’autres formats

Nous avons ici parlé du format A, mais il existe également des formats B et C.

Ainsi, les dimensions de la feuille B0 sont de 1.414 mètres de longueur et 1 mètre de largeur, puis on passe aux formats B1, B2 et ainsi de suite en pliant selon la longueur.

Outre le fait d’avoir une « valeur ronde » pour la largeur de la feuille, ce format est aussi la moyenne géométrique du format A : pour passer du format B0 au format A0, on procède à la même réduction que pour passer du format A0 au format B1, du  B1 au A1, du A1 au B2 et ainsi de suite. Les formats A et B s’intercalent ainsi régulièrement : il faut toujours multiplier ou diviser les mesures par la même quantité pour passer de l’un à l’autre.

Ce format est toutefois bien moins utilisé que le format A ou que le C, employé pour les enveloppes. Pour obtenir une enveloppe au format C0, il faut prendre cette fois la moyenne géométrique d’une feuille A0 et d’une feuille B0. Ainsi, une enveloppe C0 peut contenir une feuille A0 sans que celle-ci ne soit pliée. La même opération permet d’obtenir les formats C1, C2, C3 qui s’intercalent à chaque fois entre les formats A et B.

Format B Format C

Et puisque nous parlons d’enveloppes, autant parler d’affranchissement. Classiquement, les feuilles que nous utilisons tous les jours ont un grammage de 80 g/m². Or, nous l’avons vu, une feuille A4 correspond à 1/16 d’une feuille A0 qui elle, fait environ 1m² et pèserait donc 80 grammes.

Un petit argument de proportionnalité et hop : 80 / 16 = 5, votre feuille A4 pèse donc 5g. Un timbre seul permettant d’affranchir jusqu’à 20g, vous en déduirez combien de feuilles vous pouvez glisser dedans – mais attention à ne pas oublier de prendre le poids de l’enveloppe en compte !

Pour compléter

  • La page Wikipédia des formats de papier, d’où proviennent ces images
  • Un article du blog Wattsupscience sur les formats A
Publié dans Curiosités et récréation | Tagué , , , | Laisser un commentaire

Le code secret

Drapeau vert : Cet article ne demande aucune connaissance mathématique particulière


Comment communiquer sans être lu par des indésirables ? Cette question est à la base de ce que l’on appelle la cryptographie, destinée à protéger vos messages des regards indiscrets. Son principe est simple : remplacer le message, l’information d’origine, par un nouveau message dit chiffré que seul votre destinataire devrait être en mesure de décoder.

Tout ceci semble simple sur le papier, et pourtant… Une technique trop simple rend vulnérable votre message, alors qu’un procédé trop compliqué rend difficile sa traduction par votre correspondant.

Note : dans la suite de l’article, j’utiliserai parfois le mot « coder » ou le mot « chiffrer ». Sachez qu’ici, ils désignent la même chose, alors ne soyez pas perturbés !

Le chiffre de César

La première chose qui vient à l’esprit lorsque l’on parle de coder un message sera peut-être de tout bêtement remplacer une lettre par une autre. C’est d’ailleurs sur cette idée que se base le chiffre dit de César.

Prenons un message en clair, par exemple : « Les Mathématiques, c’est fantastique ».

Dans un premier temps, nous allons supprimer les espaces et la ponctuation. Après tout, ce sont là des signes bien trop distinctifs pour être conservé, et nous souhaitons un minimum protéger notre message. Nous souhaitons donc envoyer à notre correspondant le message : LESMATHEMATIQUESCESTFANTASTIQUE.

Le chiffrage par Code César consiste simplement à décaler toutes les lettres de cette phrase d’un certain nombre de crans fixé à l’avance. Par exemple, en décalant les lettres de trois crans, le L devient un O, le E devient un H et ainsi de suite… Si l’on doit coder la lettre Z, il suffit de reprendre au début de l’alphabet : Z -> A -> B -> C. Le Z devient donc un C.

Notre phrasé codée est donc OHVPDWKHPDWLTXHVFHVWIDQWDVWLTXH. Pour le déchiffrer, rien de plus simple : il suffit de faire l’opération inverse, c’est-à-dire de prendre, pour chaque lettre, celle qui vient trois crans avant.

Vous l’aurez sans doute compris : ce codage est trop simple ! Même sans connaître le décalage, il n’existe que 25 possibilités à tester, une broutille. Nous pourrions imaginer corser l’affaire en n’utilisant pas l’alphabet classique ABCD… mais plutôt un autre alphabet, par exemple l’ordre d’apparition des lettres sur un clavier AZERTY. En décalant de trois lettres vers la droite, le A devient R, le Z devient T, le E devient Y et ainsi de suite.

L’ennui, c’est qu’une lettre est toujours codée de la même manière. Pour déchiffrer le code, il suffit alors de regarder les fréquences d’apparition de chaque lettre, et de les analyser. En effet, en Français, la lettre la plus courante dans un texte est la lettre « E ». Il y a donc de fortes chances que la lettre qui apparaisse le plus souvent dans un texte codé de la sorte corresponde à la lettre qui code le E du message de départ.

S’il s’agit d’un code de César classique, alors le décalage est trouvé, nous pouvons retrouver le message d’origine sans peine. Regardons le message codé suivant :

DORUVTXLOUHJDUGDLWVRQHQIDQWVDPXVHUDHPSLOHUGHVFXEHVOHPDW
KHPDWLFLHQGXGOHBODQJIRUGVHSULWDREVHUYHUSOXVHQGHWDLOVODW
RXUDLQVLIRUPHHFRPSRVHHGHWURLVSDLUHVGHFXEHVGHFRXOHXUVGLIIH
UHQWHVGLVRQVMDXQHURXJHHWEOHXFHOOHFLSUHVHQWDLWXQHSURSUL
HWHTXLOWURXYDHWRQQDQWHHQWUHOHVGHXAFXEHVMDXQHVVHWURXY
DLWXQFXEHHQWUHOHVGHXAURXJHVVHQWURXYDLHQWGHXAHWHQWUHO
HVGHXAEOHXVVHQWURXYDLHQWWURLV

Comptons maintenant le nombre d’apparitions de chacune des lettres dans ce message codé.

Comptage code César

Comptage des lettres dans le message codé. La lettre k apparaît le plus souvent.

La lettre « K » est la plus fréquente : il y a de fortes chances que ce soit le codage de la lettre « E ». Pour passer du « E » au « K », il y a un décalage de 5 lettres. Il est alors possible de décoder le message, qui se trouve être le début du précédent article sur le problème de Langford.

Si l’alphabet utilisé est un peu plus complexe, il faut fournir davantage de travail. Par exemple, une fois ce E trouvé, on peut également regarder autour. Le E est souvent associé au N, il se peut que les lettres autour du E codent donc le N du message clair, et ainsi de suite. Bref, il faut compliquer notre méthode.

Le carré de Vigenère

L’idée du chiffrage de Vigenère est d’utiliser plusieurs décalages différents, selon la position de la lettre dans le message. Nous allons pour cela avoir recours à une clé -c’est-à-dire un mot qui nous servira à chiffrer et à déchiffrer notre message – et à un tableau.

Pour la clé, prenons par exemple le mot « AUTOMATHS ». Nous allons écrire le message à coder et la clé l’un au-dessus de l’autre. Evidemment, la clé n’est pas aussi longue que le message, alors nous allons la répéter jusqu’au bout, ce qui donne ceci :

Pour chiffrer le message, il suffit alors de décaler la lettre du message clair d’un nombre de cran qui dépend de la lettre de la clé correspondante, auquel on retire 1.

  • Par exemple, la première lettre du message clair est L, celle de la clé est A, qui est la 1ère lettre de l’alphabet. Je décale donc le L de (1-1) = 0 ce qui me donne toujours la lettre L.
  • Pour la suivante, E, la lettre de la clé est U, qui est la 21ème lettre de l’alphabet : je décale donc le E de 21 – 1 = 20 crans, ce qui me donne un Y, et ainsi de suite.

En codant le même message que tout à l’heure, nous obtenons :

AFHFEQNPDRYZODDTPLSIGSZFTULSUFIEEKHWMJBZQRW

LKCOUSELXTSTBXAMTBJAEHWIPLXFDAHZTARWZWPLBH
MOUZWRPXFBLNZWNXXHMIEZDANHIDABUKIZHFYEXJG
MJHGQEWLLRIBGBABYWSXXQGBXZVEWHIXENYKDCYTQR
XULEMWWEOGZBAOGSDONNWENUZQUVLDLYVWBRXZW
NNTWFUGLHRIIFUEMLIUCEHDONCSENHBZAGAWEHMFQ
LXZVEOQQGBXZBAOGSESXAJOOOOUTNUUUVXSZTKLDEM
WSGXKVMGYLGQNMYGUPTWQNMKWURXHQNMYWLYLR
QUQIDEOLGQNMYGUPTWQNMAJOCL

Le procédé peut ainsi être résumé en un tableau à double entrée : une pour la lettre du message à chiffrer, l’autre pour celle de la clé.

Tableau de Vigenère

La lettre M du message en clair est codée par la lettre O de la clé. La lettre du message codé sera donc le A.

Encore une fois, il est possible d’utiliser un autre alphabet que celui d’origine, ou une autre règle pour la conversion. Le message sera vraisemblablement plus compliqué à décoder : nous pouvons le voir en regardant de nouveau les fréquences d’apparition des lettres dans le message codé ; aucune ne semble beaucoup plus importante que les autres.

Fréquence d’apparition des lettres dans un message codé par le chiffre de Vigenère.

Pour décoder le message, il suffit alors de mettre le message codé et la clé l’un en-dessous de l’autre. Pour chaque lettre de la clé, on cherche alors la lettre du message codé, puis on remonte la colonne pour trouver la lettre du message clair.

Par exemple, si mon message codé présente un « S » codé avec la clé « K », je regarde où se situe le « S » sur la ligne du « K » dans mon tableau : cela correspond à la colonne du I.

Cette méthode est-elle pour autant infaillible ? Pas vraiment…

Ici, notre clé a 9 lettres, ce qui signifie que toutes les 9 lettres, nous utiliserons la même lettre en guise de clé. Autrement dit, dans ce cas, le chiffre de Vigenère n’est rien d’autre que 9 codes César mis côte à côte. Il est donc possible de les casser 1 par 1 pour tout décoder.

Trouver la clé

Pour autant, en règle générale, la clé est inconnue, et il n’est donc pas possible de savoir combien de décalages différents ont été utilisés pour coder le message. Il serait envisageable de toutes les tenter, de regarder si l’on arrive à quelque chose qui a du sens, mais nous sommes plus malins, n’est-ce pas ?

Rappelons donc le message que nous devons décoder :

AFHFEQNPDRYZODDTPLSIGSZFTULSUFIEEKHWMJBZQRWLKCOUSELXTSTBXAM
TBJAEHWIPLXFDAHZTARWZWPLBHMOUZWRPXFBLNZWNXXHMIEZDANHIDABU
KIZHFYEXJGMJHGQEWLLRIBGBABYWSXXQGBXZVEWHIXENYKDCYTQRXULEM
WWEOGZBAOGSDONNWENUZQUVLDLYVWBRXZWNNTWFUGLHRIIFUEMLIUCEH
DONCSENHBZAGAWEHMFQLXZVEOQQGBXZBAOGSESXAJOOOOUTNUUUVXSZ
TLDEMWSGXKVMGYLGQNMYGUPTWQNMKWURXHQNMYWLYLRQUQIDEOLGQN
MYGUPTWQNMAJOCL

Dans ce message codé, il est possible de déceler certaines suites de trois lettres – ou trigrammes – qui reviennent à différentes positions. Il y a alors deux possibilités :

  • soit il y avait deux trigrammes identiques dans le texte d’origine qui ont tous deux été codé par la même partie de la clé, aboutissant à deux trigrammes encore identiques dans le message codé.
  • soit deux trigrammes différents du message clair ont abouti par un heureux hasard à deux trigrammes identiques dans le message codé.

La probabilité de cette seconde possibilité est très faible, alors nous pouvons supposer que nous sommes dans le premier cas. En relevant alors les positions des trigrammes répétés, nous avons :

  • XZV aux positions 152 et 251
  • YGU aux positions 306 et 342

L’écart entre les deux répétitions des trigrammes est donc respectivement de 99 et 36. Or, nous avons supposé que les deux XZV étaient issus du même morceau de clé, ce qui signifie que 99 est forcément un multiple de la longueur de notre clé. C’est la même chose pour 36.

Ainsi, la longueur de notre clé est vraisemblablement un diviseur commun à 99 et à 36, ce qui ne laisse que peu de possibilités : 1, 3 ou 9. Et en l’occurrence, la longueur de la clé AUTOMATHS est de 9. Bingo, il ne reste plus qu’à décoder le tout !

Plus de complexité…

Le chiffre de Vigenère a résisté pendant près de trois siècles avant d’être enfin brisé mais est désormais facilement mis en défaut à cause de ces répétitions de la clé. Aussi, pour renforcer la sécurité, il faut utiliser une clé toujours plus longue, quitte à ce que celle-ci fasse la longueur du texte. Seulement, comment transmettre cette clé maintenant ?

C’est ici qu’intervient l’astucieux chiffrement autoclave : dans ce procédé, le message en clair fait lui-même partie de la clé !

Plus précisément, il existe bien un mot-clé, comme pour le chiffre de Vigenère, et nous choisirons toujours AUTOMATHS ici. Seulement, plutôt que de répéter cette clé à l’infini, il suffit, une fois la clé terminée, d’utiliser le message clair.

Une fois la clé placée, on répète le message lui-même : celui-ci fera office de clé pour la suite.

Pour chiffrer, on utilise alors le tableau de Vigenère. Pour décoder maintenant, on déchiffre les premières lettres grâce à la clé, puis on peut alors déchiffrer la suite grâce à ces premières lettres décodées et ainsi de suite.

Ici, plus de répétition, la méthode est robuste et tient le coup. Le seul souci, c’est qu’une seule erreur dans la transmission du message le rend impossible à déchiffrer. Attention à ne pas se tromper.

Naturellement, ce code n’est pas infaillible : le nombre de clés possibles n’est pas si élevée, mais il n’existe aucune autre astuce que de toutes les tester – hormis essayer les plus probables, mais vous ne feriez pas ça n’est-ce pas ?

Pour compléter

  • Le site Dcode vous permet de chiffrer et déchiffrer le message de votre choix avec la méthode que vous préférez
  • Un site sur le chiffre de Vigenère qui contient un mémoire assez complet sur la question
Publié dans Cryptographie | Tagué , , , | Laisser un commentaire

Le problème de Langford

Drapeau vert : Cet article ne demande aucune connaissance mathématique particulière


Alors qu’il regardait son enfant s’amuser à empiler des cubes, le mathématicien Dudley Langford se prit à observer plus en détails la tour ainsi formée. Composée de trois paires de cubes de couleurs différentes – disons jaune, rouge et bleu – celle-ci présentait une propriété qu’il trouva étonnante : entre les deux cubes jaunes se trouvait un cube, entre les deux rouges s’en trouvaient deux, et entre les deux bleus s’en trouvaient trois.

Solution au problème de Langford pour 3 couleurs

L’histoire aurait pu s’arrêter là, mais les mathématiciens s’arrêtent rarement aux cas particuliers ! Non, le mathématicien est un éternel insatisfait qui cherche toujours une généralisation de son problème.

Prenons alors un ensemble composé de n paires de cubes, chacune d’une couleur différente des autres paires. Pour que tout soit plus commode, nous allons numéroter ces couleurs de 1 à n, et pourrons alors désigner chaque cube soit par sa couleur, soit par un numéro.

Est-il alors possible de disposer ces cubes en ligne de telle sorte qu’il y ait exactement 1 espace entre les cubes de la couleur 1, 2 espaces entre les cubes de la couleur 2, 3 espaces entre les cubes de la couleur 3, et ainsi de suite ?

En essayant avec 4 couleurs, nous pouvons, avec un peu de réflexion, arriver à un résultat convenable. A vrai dire, pour 3 ou 4 couleurs, le résultat obtenu est unique – si l’on considère que lire la ligne de droite à gauche ne donne pas une solution différente. Vous devriez donc parvenir à cette solution, ou à son écriture « renversée » :

Solution au problème de Langford pour 4 couleurs.

Malheureusement, pour 5 couleurs, on piétine. Même chose avec 6 couleurs, alors que lorsque l’on en prend 7, il est possible de trouver plusieurs arrangements qui respectent les règles de Langford.

Deux solutions au problème de Langford à 7 couleurs.

Au total, on comptabilise 26 solutions au problème de Langford à 7 couleurs, 150 solutions pour le problème à 8 couleurs… Et de nouveau aucune pour 9 et 10 couleurs !

Le problème ne trouve aucune solution pour 13 et 14, pour 17 et 18, 21 et 22, et ainsi de suite…

Des puzzles parfois impossibles

Attention, voilà les lettres !

Considérons que nous avons n paire de cubes, soit 2n au total, que nous souhaitons faire loger dans autant d’emplacements. Nous devons ainsi créer des espacements de 1 cube, 2 cubes, 3 cubes, et ainsi de suite jusqu’à n cubes.

Premièrement, notons que parmi les nombres entiers entre 1 et 2n, il y a autant de nombres pairs que de nombres impairs. Raisonnons alors selon les espaces à laisser entre les cubes.

Si je place le premier cube portant le numéro a à la position x, alors l’autre cube sera placé à la position x + a + 1. En effet, entre les nombres x et x + a + 1, il y a exactement a cubes. Par exemple, si je place le cube 5 en position 2, le second cube portant le numéro 5 sera à a position 5 + 2 + 1, soit 8.

Si a est pair, alors les nombres x et x + a + 1 seront de parité différentes : si l’un est pair, l’autre sera impair. Sur la première solution donnée pour 7 couleurs, on voit que les cubes portant le numéro 4 se trouvent aux positions 2 (pair) et 7 (impair).

Inversement, si a est impair, alors les nombres x et x + a + 1 seront de même parité : soit tous les deux pairs, soit tous les deux impairs. On l’a vu, il nous faut autant de positions paires que de positions impaires dans notre arrangement : par conséquent, chaque a qui produit un écart entre deux positions paires doit être en quelque sorte « compensé » par un a qui produit un écart entre deux positions impaires.

On en conclut que le nombre de a impairs doit, lui, être pair ! Ceci arrive uniquement lorsque l’entier n ou l’entier n + 1 est un multiple de 4.

Prenons alors le cas de 14 couleurs, soit 28 cubes. 14 et 15 ne sont pas des multiples de 4, il n’est donc pas possible de résoudre le problème à 14 couleurs

Nous pouvons vérifier à la main : il doit donc y avoir des écarts de 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13 et 14 cubes. Les nombres impairs sont 1, 3, 5, 7, 9, 11, 13 : il y en a 7, un nombre impair.

Construire une solution

Cette démonstration permet simplement d’affirmer l’impossibilité de résoudre certains puzzles, mais elle n’affirme en aucun cas que tous les autres peuvent trouver une solution.

Rassurez-vous, il existe bel et bien un moyen de construire une telle solution dans les autres cas, donnée par Roy Davies. Pour trouver sa solution, celui-ci a remarqué certains motifs particuliers, qu’il a ensuite complété.

Par exemple, la suite 4 2 _ _ 2 4 respecte les règles de Langford. On peut par ailleurs rajouter un 6 de chaque côté sans pour autant enfreindre une règle, et le motif devient alors 6 4 2 _ _ 2 4 6… Puis on peut faire 8 6 4 2 _ _ 2 4 6 8 et ainsi de suite avec tous les nombres pairs. La même chose peut être faite en utilisant les nombres impairs, aboutissant par exemple à la suite 7 5 3 1 _ 1 3 5 7. Davies va ainsi mélanger les motifs avec les nombres pairs et impairs, en les séparant en deux tas.

Les lignes rouges relient des nombres pairs, les lignes bleues, des nombres impairs. La hauteur de la ligne dépend de la valeur du nombre. Source : Langford’s problem, remixed, John Miller.

Voyons par exemple la méthode pour n = 20 = 4 x 5.

D’abord, on met de côté les trois plus grands nombres, nous mettrons de côté 18, 19 et 20. Nous mettrons également de côté le nombre 2 x 5 – 1, soit le nombre 9

Nous allons maintenant construire 4 sous-ensembles avec les nombres restants :

  • les nombres pairs supérieurs ou égaux à n/2 : 10, 12, 14, 16
  • les nombres impairs plus grands que n/2 : 11, 13, 15, 17
  • les nombres pairs strictement inférieurs à n/2 : 2, 4, 6, 8
  • les nombres impairs strictement inférieurs à n/2 : 1, 3, 5, 7

Puis, il faudra utiliser le principe montré plus haut et réorganiser ces nombres pour obtenir des combinaisons « valables ». Nous obtenons alors 4 séquences :

  • 16 14 12 10 _ _ _ _ _ _ _ _ _ _ 10 12 14 16
  • 17 15 13 11 _ _ _ _ _ _ _ _ _ _ _ 11 13 15 17
  • 8 4 6 2 _ _ 2 4 6 8
  • 7 5 3 1 _ 1 3 5 7

Une fois arrivés ici, nous allons emboîter la petite séquence impaire dans la grande séquence paire, et inversement. Nous mettrons les deux côte à côte avec un espace au milieu. Cela nous donne alors la séquence qui suit :

16 14 12 10 _ 7 5 3 1 _  1 3 5 7 10 12 14 16 _ 17 15 13 11 _ 8 6 4 2 _ _ 2 4 6 8 11 13 15 17 _ _

Il suffit alors de compléter les trous avec les paires des trois plus grands nombres, dans l’ordre. Les trous restants correspondent alors au 9 que nous avons retiré.

16 14 12 10 18 7 5 3 1 19  1 3 5 7 10 12 14 16 20 17 15 13 11 18 8 6 4 2 9 18 2 4 6 8 11 13 15 17 20

Vous pouvez reprendre le principe pour n’importe quel nombre de la forme n = 4k. Pour ceux de la forme n = 4k – 1, reprenez le même principe en enlevant les deux nombres les plus grands, ainsi que le nombre 2k – 1.

Pour compléter

  • La note de Dave Moore qui essaye de trouver un autre procédé pour construire une suite valide.
  • Une page qui recense toutes les avancées faites sur les problèmes de Langford et leurs généralisations.
  • Une animation Geogebra de la construction d’une suite valide, utilisant la méthode de Davies
Publié dans Curiosités et récréation | Tagué , , , | 1 commentaire

Le dernier des premiers

Drapeau jaune : Cet article demande quelques connaissances mathématiques et un peu d’abstraction pour être entièrement compris


Les nombres premiers sont fascinants. Pour rappel, un nombre entier supérieur à 0 est dit premier s’il possède exactement deux diviseurs, à savoir 1 et lui-même. Et ces nombres sont aujourd’hui utiles dans notre quotidien, puisqu’ils sont à la base du système de cryptographie RSA, garant de votre (presque) sécurité informatique.

Dans un précédent article, je vous parlais des théorèmes et conjectures concernant leur répartition au sein de l’ensemble des nombres entiers. En particulier, l’ensemble des nombres premiers est infini : peu importe le nombre premier considéré, il en existe toujours un plus grand.

Et face à ce genre de résultat, les compétitions fusent pour trouver et décrire au mieux les plus grand nombres premiers possibles. Le record a d’ailleurs été battu très récemment, ce 3 janvier 2018 : il est désormais acquis que le nombre suivant est premier :

277232917-1

Alors, c’est bien gentil, mais d’où ça vient tout ça ?

Les nombres de Mersenne

Marin Mersenne

Marin Mersenne, religieux français ayant donné son nom aux nombres qui nous intéressent aujourd’hui.

Parmi les nombres premiers, il existe certaines sous-familles plus ou moins remarquables, et parmi celles-ci figurent les nombres de Mersenne premiers.

Un nombre de Mersenne est un nombre qui peut s’écrire sous la forme 2p – 1, où p est un entier strictement positif. Ce nombre est plus simplement noté Mp. Par exemple, 7 peut s’écrire 7 = 23 – 1, c’est donc un nombre de Mersenne, et on le notera, conformément à ce que nous avons écrit plus tôt, M3. Vous l’aurez alors sans doute deviné, un nombre de Mersenne premier est un nombre qui est à la fois de Mersenne et premier. C’est le cas de 7, mais aussi de 3, de 31, où de notre nouveau nombre premier record.

Pour qu’un nombre de Mersenne Mp soit premier, il faut avant tout que l’entier p soit lui-même premier. Par exemple, M4 ou M42 ne peuvent être des nombres premiers, puisque 4 et 42 ne le sont pas eux-mêmes.

Cette condition est toutefois loin d’être suffisante !
Par exemple, le nombre M11 = 211 – 1 = 2047 = 23 x 89 et n’est donc pas premier.

Revenons en au nombre qui nous intéresse : 277232917-1. Ce nombre est en réalité le 50ème nombre de Mersenne premier qui a été démontré comme étant premier à ce jour. Attention, cela ne signifie pas qu’il y en a exactement 49 qui soient plus petits que celui-ci : d’autres ont pu échappé aux mailles du filet !

Toujours est-il que ce nombres est grand, très grand : pour l’écrire en entier, il vous faudrait écrire pas moins de 23 millions de chiffres (23.249.525 pour être exact). Si vous préférez le binaire, vous pouvez également vous amuser à écrire 77.232.917 fois le chiffre 1.

Pour vous faire passer cette folle envie, sachez que sur un Document Word écrit en Times New Roman, avec une taille de police de 10 et les marges classiques, il vous faudra pas moins de 3845 pages pour en venir à bout… Bon courage !

Et si l’on remonte dans le temps, il s’avère que les précédents nombres premiers records étaient également des nombres de Mersenne. Il doit bien y avoir une raison derrière tout cela !

Le test de Lucas-Lehmer

En effet, inutile de vous cacher la vérité plus longtemps, il y a bien un secret. Naïvement, pour prouver qu’un nombre est premier, on peut regarder tous les entiers entre 2 et ce nombre, et montrer qu’aucun de ceux-ci ne divise notre nombre. Si l’on est un peu plus futé, on arrêtera cet algorithme à la racine carrée du nombre… Mais tout ceci est affreusement long !

C’est d’ailleurs sur cette longueur que repose la cryptographie actuelle : trouver un nombre premier, factoriser un nombre en produit de nombres premiers est faisable mais très long, mais une fois que la solution est donnée, il est très aisé de la vérifier.

Cette difficulté n’est pas la même pour tous les nombres, et en particulier pour les nombres de Mersenne. Pour cela, faisons appel à la suite de Lucas-Lehmer, que nous nommerons S, et définie comme suit :

  • S(1) = 4
  • Pour tout n>1, S(n + 1) = S(n)² – 2

    Edouard Lucas

    Edouard Lucas a créé un premier test de primalité…

Autrement dit, le premier terme de cette suite vaut 4, et chaque terme de la suite est égal au carré du terme précédent auquel on retire 2. Les premiers termes sont les suivants :

4 ; 14 ; 194 ; 37.634 ; 1.416.317.954…

Pour vérifier si un nombre nombre de Mersenne Mp est premier, nous allons regarder le (p-1)-ième terme de cette suite, S(p-1). Si Mp divise S(p-1), alors Mp est premier ! Et réciproquement, si Mp ne divise pas S(p-1), alors Mp n’est pas premier.

Par exemple, 7 = 23 – 1 = M3. Nous regardons le deuxième terme de la suite de Lucas-Lehmer, celui-ci vaut 14 et est bien un multiple de 7 : M3 divise S(2), M3 est bien premier.

Derrick Lehmer

.. Un test de primalité amélioré plus tard par Derrick Lehmer.

Cependant, les nombres de la suite de Lucas-Lehmer grandissent très vite, trop vite pour être utilisés ainsi. Ainsi, il sera bien plus efficace d’utiliser seulement les « restes » de la suite de Lucas-Lehmer, modulo le nombre qui nous intéresse. Cette notion, si vous avez déjà parcouru le blog, vous l’avez rencontrée à plusieurs reprises, mais je vais tout de même en rajouter une couche.

Considérons par exemple M13 = 8191. On se pose alors la question « Est-ce que le 12 ème terme de la suite de Lucas-Lehmer est un multiple de 8191 ou pas ? ». Que ce soit le cas ou non, lui ajouter ou lui retirer 8191 ne changera pas la conclusion : nous allons donc lui retirer un maximum de fois le nombre 8191, jusqu’à obtenir un nombre plus petit que celui-ci.

Une autre manière de l’imaginer, c’est de se dire que nous comptons en boucle : après 8190 vient 0, et on recommence ainsi. C’est ce que l’on nomme l’arithmétique modulaire. Et plutôt que de le faire seulement au 12ème nombre, nous allons faire ce calcul à toute la suite : nous allons exprimer la suite de Lucas-Lehmer modulo 8191.

  • S(1) = 4, cela ne change pas. De même, S(2) = 14 et S(3) = 194
  • En revanche, S(4) = 37.634, ce qui est plus grand que 8191. Nous allons donc réduire ce nombre modulo 8191, et le calcul nous donnera S(4) = 4870 (modulo 8191)
  • Nous repartons alors de ce nombre-ci ! S(5) = 4870² – 2 = 23716898. Un petit coup de modulo 8191 et nous avons notre 5ème terme, S(5)= 3953 (modulo 8191)
  • Et ainsi de suite, notre suite vaudra 5970, 1857, 36, 1294, 3470, 128…
  • Jusqu’au douzième terme qui vaut 0, ce qui signifie que le nombre de la suite « classique » était en effet un multiple de 8191
  • Finalement, M13 est premier !

Vous n’avez peut-être pas tout compris, et ce n’est pas bien grave : l’important est que nous disposons, pour les nombres de Mersenne, d’une méthode simple et efficace pour déterminer si oui ou non, un nombre de Mersenne est premier.

Chasseur de « primes »

(Oui, alors, en anglais, un nombre premier se dit « prime number ». Du coup, je jugeais opportun de placer ce petit jeu de mot, mais le fait de devoir l’expliquer tend à montrer le contraire !)

Bref, nous avons une méthode efficace pour déterminer si un nombre donné est premier ou pas : pas étonnant que ce soient les nombres de Mersenne qui battent des records !

D’ailleurs, le programme qui permet de déterminer si un nombre de Mersenne est premier est en libre service : vous pouvez, avec votre propre ordinateur, partir à la recherche de nombres premiers toujours plus grands [voir liens plus bas]. Mieux, vous pouvez même être récompensés, histoire d’arrondir les fins de mois. Comptez toutefois un certain temps, plus ou moins long, avant d’arriver à destination.

Finissons sur une note plus rabat-joie : hormis le fait de dire « Ouah, on a découvert un super grand nombre premier », l’arrivée de ce nouveau nombre de Mersenne ne bouleverse pas le paysage mathématique. En effet, vu la « simplicité » de ce nombre, il n’y a absolument aucune chance de le voir utiliser en cryptographie par exemple… Mais peut-être son utilité sera-t-elle revue un jour !

Pour compléter

  • Envie de lecture ? Regardez cette vidéo de Numberphile qui présente l’ancien plus grand nombre premier connu.
  • L’annonce de la découverte du 50ème nombre de Mersenne premier
  • Vous aussi, découvrez des nombres premiers toujours plus grand avec le logiciel du Great Internet Mersenne Prime Research (GIMPS)
  • Trouver des grands nombres premiers, un problème de tous les jours, sur Science étonnante
Publié dans Actualité, Les Nombres | Tagué , , | 3 commentaires

Suite logistique et arbre chaotique

Drapeau jaune : Cet article demande quelques connaissances mathématiques et un peu d’abstraction pour être entièrement compris


Il arrive parfois que des relations d’apparence très simples aboutissent à des comportements extrêmement complexes. A titre d’exemple, intéressons-nous aujourd’hui à ce que l’on nomme la suite logistique.

Modéliser une population

Comme son nom ne l’indique pas forcément, la suite logistique vise à estimer l’évolution de la taille d’une population au cours du temps. Peu convaincu par le modèle de Malthus, qui utilise un taux de croissance constant de la population, le mathématicien Pierre François Verhulst imagine, en 1840, un tout autre modèle qui introduit une part de concurrence.

En effet, on imagine bien que, dans de bonnes conditions, la taille de la population d’une espèce donnée tend à augmenter. Seulement, lorsque cette taille est trop importante alors que les ressources disponibles n’augmentent pas, de la compétition se met en place entre les individus, ce qui aboutit alors à une diminution de la taille de population.

Si, une année, une population se trouve en deça d’un certain seuil, alors l’année suivante, la population sera plus importante. Si, à l’inverse, elle se trouve au-delà, alors la compétition et la concurrence la fera baisser l’an suivant.

Pour modéliser cela, Verhulst propose une formule toute simple. Appelons P(n) la taille de population de notre espèce à l’année n. Nous pouvons redimensionner cette population pour que ce nombre soit compris entre 0 et 1 (en divisant tout simplement par la population maximale). 0 correspond à une extinction de la population, 1 signifie que la population a atteint son niveau maximal. Alors :

P(n+1) = R x P(n) x (1 – P(n))

où R est une constante qui dépend de l’espèce que nous souhaitons modéliser.

Par exemple, choisissons R=2, et une population de départ de taille P(0) = 0.2

  • Après la 1ère année, la population P(1) sera de R x P(0) x (1 – P(0)) soit 2 x 0.2 x 0.8, soit 0.32
  • Recommençons en partant de 0.32. Après la deuxième année, la taille de notre population sera donc de 2 x 0.32 x (1 – 0.32) ce qui vaut 0.4352
  • Puis elle vaudra 0.4916019
  • Puis 0.4998589
  • Puis elle vaudra 0.5, et à l’étape suivante, encore 0.5, et ainsi de suite, jusqu’à la fin des temps.

Evolution de la taille de population pour R = 2

Chaque nouvelle application de la formule s’appelle une itération, et lorsque nous itérons suffisamment le procédé, nous observons que la taille de population se stabilise aux alentours d’une taille limite. Dans le cas où R=2 et P(0)=0.2, cette valeur limite vaut 0.5.

Changeons alors la valeur de notre R et observons le comportement de la taille de la population. Pour R = 2.9, la population se stabilise autour de 0.655, tout en oscillant autour de cette valeur.

Pour un R trop faible, plus petit que 1, le population atteindra 0 : c’est l’extinction, claire et nette, aucun survivant.

Prenons maintenant R=3.1 et regardons les tailles de population au cours du temps :
0.2 ; 0.496 ; 0.7749504 ; 0.5406471  ; 0.7698782 ; 0.5492138 ; 0.7674918 ; 0.5531892…

Evolution de la taille de population pour R = 3.1

Cette fois, nous n’observons plus une mais deux valeurs qui se répètent indéfiniment et la taille de notre population passe de l’une à l’autre, d’une année sur l’autre. Passons alors à 3.5 et observons :

Evolution de la taille de population pour R = 3.5

Cette fois, notre taille de population se met à osciller indéfiniment entre 4 valeurs. Et en augmentant encore notre R, nous pourrions trouver des oscillations entre 8, 16, 32 valeurs… Jusqu’à trouver le chaos le plus total !

Diagramme de Feigenbaum

Nous allons construire un graphique avec, sur l’axe horizontal, la valeur du paramètre R et, sur l’axe vertical, les valeurs autours desquelles la population semble se stabiliser ou osciller. La figure obtenue, appelée diagramme de Feigenbaum, du nom du mathématicien qui l’étudia, ressemble à ceci :

Diagramme de Feigenbaum

Avant la valeur de R = 3, il n’y a qu’une seule valeur stable, comme c’était le cas pour notre premier essai. Puis, à partir de ce point, le graphe se scinde en deux parties, les deux valeurs que prend la taille de population. Puis, aux alentours de R = 3.45, ces deux branches se dédoublent de nouveau, donnant naissance à 4 branches, puis 8 un peu plus tard.

On peut constater que ces dédoublements sont de plus en plus rapprochés, mais surtout qu’à partir de R = 3.57, la population va alterner entre une infinité de valeurs, sans période précise : c’est le chaos.

Un peu d’ordre dans le chaos

Malgré le désordre ambiant, le diagramme de Feigenbaum (ou figuier, comme certains le nomment) possède plusieurs propriétés intrigantes.

Zoomons par exemple autour de l’embranchement supérieur : on retrouve exactement la même structure que notre arbre de départ. Le graphe contient plusieurs versions miniatures de lui-même.

Le graphique contient plusieurs versions miniatures de lui-même.

L’ordre reprend par ailleurs ses droits pour certaines valeurs isolées, que nous pouvons apercevoir sur les zones plus clairs du diagramme. Ainsi, en prenant un R d’environ 3.83, on se retrouve avec une oscillation de période 3.

Evolution de la taille de population pour R = 3.83

En vérité, le résultat est plus puissant que cela : les périodes dans un tel diagramme apparaissent dans un ordre très précis, appelé Ordre de Charkovski. Au début, la période était de 1, puis de 2, puis de 4, et ainsi de suite. La dernière période de ce classement est justement la période 3. Autrement dit, si quelque part dans le graphe se trouve un cycle de période 3, alors toutes les autres périodes s’y trouvent (et elles s’y trouvent avant, soit entre R = 0 et R = 3.83 dans notre cas).

Un autre exemple d’ordre dans le chaos ? Nous avons plus tôt mentionné que les temps de dédoublement étaient de plus en plus courts… et il s’avère que ces temps obéissent en fait à une loi très précise. Appelons B(n) la valeur de R pour la n-ième bifurcation, alors le rapport B(n)/B(n+1) tend vers une certaine constante δ appelée Nombre de Feigenbaum, et qui vaut environ 4,6692016…

Et cette constante n’est pas inhérente à notre cas : si nous choisissons une autre suite que notre suite logistique, pourvu qu’elle respecte certaines propriétés, alors nous obtiendrons le même comportement pour notre taille de population, un diagramme semblable, un comportement qui finit par devenir chaotique, mais aussi un rapport entre les temps de bifurcation qui se rapproche de cette même constante.

Voici par exemple le résultat quand nous prenons P(n + 1) = R x sin( π x P(n) )

Oui, c’est presque pareil… Et nous aurons la même allure pour toute fonction dont la courbe forme une « bosse » comme le font les deux précédentes. A vous de choisir celle que vous préférez alors.

Pour compléter

Envie d’explorer un peu plus le chaos ?

Publié dans Curiosités et récréation, Mathématiques appliquées | Tagué , , , | Laisser un commentaire

De l’autre côté du zéro…

Drapeau rouge : Cet article demande quelques connaissances mathématiques intermédiaires ainsi qu’une bonne capacité d’abstraction


Attention, abstraction ! Vous êtes prévenus

Frege, Peano, Von Neumann et d’autres… Les entiers naturels ont leur construction et les opérations classiques d’addition et de multiplication sont bien définies pour chacune d’entre elles.

Vous pouvez trouver celle de Peano à cette adresse, celle de Frege ici, et la construction de l’addition par là.

Sans surprise nous retrouvons alors le fait que 5+3=8, 1+1=2 et ainsi de suite. En revanche, quel est le nombre x tel que 2+x=7 ? Si le nombre 5 nous vient immédiatement à l’esprit, posons-nous la question de son arrivée, de sa décision. Intuitivement, nous avons fait l’opération 7-2, autrement dit une soustraction… laquelle n’est pas encore proprement définie dans notre ensemble.

Les nombres négatifs sont dans notre quotidien, mais cela n’a pas toujours été le cas.

Plus généralement, et même si leur acceptation a tardé à venir, nous avons conscience aujourd’hui de l’existence de nombres négatifs : qu’il s’agisse de la température ou des étages d’un immeuble, le signe « moins » devant un nombre ne nous est pas étranger. Là encore, nous pourrions interpréter l’entier négatif -2 comme étant le résultat de la soustraction entre 0 et 2, et nous revenons à notre point de départ : c’est quoi une soustraction ?

Pire encore, puisque -2 est aussi le résultat de la soustraction entre 3 et 5, quelle écriture doit-on privilégier ?

Des classes d’équivalence

Pour s’en sortir, le mathématicien Richard Dedekind utilisera alors le raisonnement que nous avons posé en introduction, à savoir qu’un entier relatif peut s’écrire, de manière non unique certes, comme la différence de deux nombres entiers naturels.

Richard Dedekind

Pour s’affranchir de la soustraction tout d’abord, il notera plutôt cette différence comme un couple d’entiers naturels (a,b). Ainsi, au lieu d’écrire 2 – 5 comme nous serions tentés de le faire, Dedekind notera simplement ce nombre (2,5). De même, 4 – 3 devient (4,3),     7 – 10 devient (7,10) et ainsi de suite.

L’ennui, comme mentionné, est la multiplicité des écritures des entiers relatifs avec cette convention. (2,5) et (7,10) désignent par exemple le même entier, -3. Lorsqu’un objet mathématique possède plusieurs écritures possibles, les mathématiciens adorent trouver une relation d’équivalence qui relie chacune de ces écritures : ainsi peuvent-ils noter l’objet en question comme une classe d’équivalence, ce qui résout tous les problèmes d’unicité si ennuyeux. N’hésitez pas à lire cet article si cette notion vous est étrangère.

Quelle relation trouver alors ? Si deux couples (a,b) et (c,d) désignent le même entier relatif, alors a – b = c – d, par construction. Seulement, puisque nous n’avons pas le droit d’utiliser la soustraction, nous pouvons modifier légèrement l’écriture, ce qui nous donnera a + d = c + b. C’est la relation que nous utiliserons :

Deux couples d’entiers naturels
(a,b) et (a’,b’) sont en relation – ce que l’on notera désormais (a,b) ∼ (a’,b’) si a+b’=a’+b

Cette relation est-elle bien une relation d’équivalence ? Autrement dit, vérifie-t-elle bien les trois propriétés de réflexivité, de symétrie et de transitivité que nous avons mentionné
sur la page concernée ?

  • Quel que soit le couple d’entier (a,b), on a évidemment (a,b) ∼ (a,b). Cela revient à écrire que a+b=a+b. Youpi.
  • Quels que soient les couples d’entiers (a,b) et (a’,b’), si a + b’= a’ + b, alors a’ + b = a+ b’, autrement dit si (a,b) ∼ (a’,b’), alors (a’,b’) ∼ (a,b)
  • Soient les couples d’entiers (a,b), (a’,b’) et (a’ ‘,b’ ‘) et supposons que (a,b) ∼ (a’,b’) et que (a’,b’) ∼ (a’ ‘,b’ ‘)
    Cela se traduit par a + b’ = a’ + b et a’ + b’ ‘ = a’ ‘ + b’. Alors, en combinant ces deux égalités, nous avons
    a + b’ + a’ + b’ ‘ = a’ + b + a’ ‘ + b’, ce que l’on réécrit
    a + b’ ‘ + a’ + b’ = a’ ‘ + b + a’ + b’.

Et là, il ne faut pas aller trop vite. Peut-on alors retirer les a’ + b’ de chaque côté, sans avoir accès à la soustraction ? C’est bien le cas, et vous pouvez vous amuser à le montrer, mais cela n’a rien d’évident !

On peut alors représenter ces classes d’équivalence sur une grille d’entiers naturels : les entiers naturels que l’on construit sont en fait représentées par les diagonales de cette grille. Certains jumeaux bien connus vous diront peut-être qu’en voyant cela, Dedekind comprit tout de suite que le Monde était dirigé par l’équation d’une droite qui se reproduisait dans deux dimensions orthogonales plus une invisible, mais je ne me lancerai pas sur ce genre d’ineptie… Oups, trop tard.

Les classes d’équivalence pour notre relation correspondent au diagonale du plan.

Chaque entier relatif peut alors être désigné par l’un des membres de la classe d’équivalence qu’il désigne (on parle de représentant). Classiquement, on choisira (n,0) pour un entier positif et (0,n) pour l’entier négatif -n, mais rien n’empêche d’en choisir un autre.

Des opérations

Maintenant que nous avons nos entiers relatifs, nous pouvons définir une addition sur ces nouveaux nombres. Pour ce faire, faisons de nouveau comme si la soustraction existait. Le couple (a,b) désigne donc le nombre a – b et le couple (a’,b’) désigne le nombre a’ – b’.

Si on souhaite additionner ces nombres, nous avons, en réorganisant les termes,
(a,b) + (a’,b’) = (a – b) + (a’ – b’) = (a + a’) – (b + b’), ce qui s’écrit avec notre convention d’écriture (a,b) + (a’,b’)=(a + a’,b + b’).

Autrement dit, il suffit d’ajouter terme à terme nos deux nombres.

Par ailleurs, on peut remarquer que (a,b) + (b,a) = (a + b, a + b) = 0. Il est alors possible de définir l’opposé et la soustraction entre deux nombres :

(a,b) – (a’,b’) = (a,b) + (b’,a’) et -(a,b) = (b,a)

Pour la multiplication, on peut procéder au même jeu de réécriture :
(a – b).(a’ – b’) = a.a’ – a.b’ – b.a’ + b.b’ = (a.a’ + b.b’) – (a.b’ + b.a’), ce que nous réécrivons
(a,b).(a’,b’) = (a.a’ + b.b’,a.b’ + b.a’).

Cette multiplication est, par ailleurs, distributive par rapport à l’addition :
a(b + c) = ab + ac pour n’importe quels entiers relatifs a,b et c

L’ensemble \mathbb{Z} muni de ces deux opérations d’addition de multiplication est appelé « anneau » et est parfois noté (\mathbb{Z},+,.)

Contrairement à l’addition qui permet de définir la soustraction, nous ne pouvons pas définir la division de deux entiers relatifs, et ce pour une raison simple : cette division ne donne pas forcément un entier relatif lui-même.

En revanche, nous pouvons démontrer ce que l’on nomme l’intégrité de l’anneau (\mathbb{Z},+,.). Ce terme signifie que si le produit de deux entiers relatifs est nul, alors
au moins l’un des entiers relatifs est nul.

Récapitulons

Pour tous entiers relatifs (a,b) et (a’,b’), on définit :

  • (a,b)+(a’,b’)=(a+a’,b+b’)
  • (a,b)-(a’,b’)=(a,b)+(b’,a’)
  • (a,b).(a’,b’)=(a.a’+b.b’,a.b’+a’.b)
  • Si (a,b).(a’,b’)=0 alors a=b ou a’=b’

Grâce à ces opérations, nous pouvons obtenir les règles de signes basiques. Par exemple, si l’on multiplie deux entiers négatifs notés (0,a) et (0,b), on obtient le nombre (a.b,0), qui est positif.
C’est une démonstration du fait connu que « moins par moins fait plus ».

Publié dans Les Nombres | Tagué , , | Laisser un commentaire