[Vidéo] De l’ordre dans les tiroirs

Voilà, je me lance dans l’arène ! La première vidéo Automaths est disponible depuis presque une semaine maintenant sur Youtube et concerne un principe simple et pourtant redoutablement efficace : le principe des tiroirs !

Vous souhaitez aller un peu plus loin ? Voici peut-être de quoi satisfaire votre curiosité !

La vidéo est classée Drapeau vert, accessible à tous, mais les précisions qui suivent tiennent davantage du Drapeau rouge.

Rationnels et périodes

Parmi les nombres dits réels, il existe deux sous-catégories de nombres : ceux dits rationnels, qui peuvent s’écrire sous la forme d’une fraction, résultats d’une division de deux nombres entiers, et les irrationnels, ceux qui ne le peuvent pas.

Dans la première catégorie se rangent ainsi les nombres comme 1/3, 47/99 ou 42/187. Ces nombres, si on essaye de les écrire sous leur forme décimale, ont une propriété intéressante :

1/3 = 0.3333333…
47/99 = 0.4747474747…
42/187 = 0.224598930481283422459893048128342245989304812834…

Pourvu que notre calculatrice aille assez loin, on voit apparaître une suite de chiffres qui se répète à l’infini : c’est ce que l’on nomme la période. Il s’avère en fait que tout nombre rationnel, toute fraction, possède une écriture décimale périodique. Et il s’avère que c’est une conséquence du principe des tiroirs !

En effet, lorsque l’on fait une division décimale, soit il n’y a pas de reste, et on s’arrête là : la suite du nombre n’est donc qu’une infinité de zéro après la virgule.

Soit on ne s’arrête jamais. Or, les restes de la division sont toujours inférieurs au dénominateur (il ne peut pas rester 48 morceaux si l’on essaye de partager en 47 parts : en effet, il suffit de retirer de nouveau 47 morceaux et en donner un à chacun. C’est tout de même plus cool non ?)

Nous avons donc un nombre fini de reste possibles alors que notre développement se poursuit à l’infini. Si l’on développe alors le quotient p/q, il n’y a donc que q – 1 restes possibles, allant de 1 à q – 1 (on a exclu le cas du reste valant 0 un peu plus haut). Fatalement, il y aura, au sein des q premières étapes de la division, au moins deux restes identiques, c’est le principe des tiroirs qui nous le dit !

Et puisque la division ne dépend pas de ce qu’il se passe avant ce stade, forcément, les développements à partir de ces deux étapes aux restes identiques sera le même.

Approcher des rationnels

Dans la deuxième catégorie, celle des irrationnels, entrent par exemple √2, π, e et bien d’autres encore. Dans un certain sens, ils sont d’ailleurs bien plus nombreux que les nombres rationnels, mais c’est une autre histoire.

En revanche, il est possible d’utiliser les nombres rationnels pour les approcher d’aussi près que l’on veut. Une méthode est par exemple de prendre ce que l’on appelle les « développements décimaux tronqués ». Par exemple, √2 = 1.41421356237… avec des décimales qui continuent ainsi à l’infini. Ainsi, la suite 1, 1.4, 1.41, 1.414, 1.4142 est une suite de nombres rationnels (et mêmes décimaux) qui approche de plus en plus finement le nombre √2. Seulement, cette approche n’est pas efficace, dans le sens où les dénominateurs de ces fractions sont grands – et donc, les numérateurs sont obligés de suivre. On aimerait ainsi gagner en précision tout en restant avec des dénominateurs raisonnables, plus agréables pour des calculs à la main, comme dans l’ancien temps.

Par exemple, le nombre π a souvent été remplacé par la fraction 22/7 qui est la meilleure approximation au sens où, pour tout dénominateur plus petit que 7, l’approximation de π sera forcément moins bonne.

L’approche de Dirichlet utilisant le principe de tiroirs permet ainsi de contrôler ce dénominateur : si je me donne un entier n et un réel x, je peux approcher ce réel avec une fraction p/q telle que l’erreur est inférieure à 1/nq, mais surtout avec un dénominateur q inférieur à n.

Alors, c’est bien gentil, mais le principe des tiroirs dans tout ça, où intervient-il ?

Pour un nombre, on peut s’intéresser à sa partie fractionnaire, c’est-à-dire, celle qui vient après sa virgule. La partie fractionnaire de 1.5 est 0.5, celle de 1.4978 est 0.4978 et ainsi de suite. Cette partie fractionnaire se situe donc entre 0 et 1, 1 étant exclu, ce que l’on note [0;1[. On notera la partie fractionnaire d’un nombre A entre accolades : {A}.

Nous allons donc regarder les parties fractionnaires {0x}, {1x}, {2x}, {3x}, et ainsi de suite jusqu’à {nx} – il y en a en tout n + 1.

Or, il est possible de découper l’intervalle [0 ; 1 [ en n plus petits intervalles : [0;1/n[, [1/n;2/n[, … [(n-1)/n;1[. Ainsi, si l’on veut ranger les n+1 parties fractionnaires dans les n intervalles construits, il y aura forcément un intervalle qui contiendra deux de ces parties fractionnaires.

Ainsi, on a deux nombres différents, k et h, telles que la différence |{hx} – {kx}| est inférieure à 1/n. Il suffit alors de choisir comme nombre p la différence entre les parties entières de kx et hx, puis comme nombre q la quantité q = k – h, et on aura alors :

|x – p/q| < 1/nq

Ouf, c’est terminé !

Pour compléter

  • L’excellent article de Jean-Paul Delahaye dans Pour la Science de Janvier 2018 (n°483)

 

 

 

Publié dans Vidéo | Tagué , , | Laisser un commentaire

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

Les pavages dorés

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


Une envie subite de refaire votre papier peint ou le carrelage de votre salle de bain ? En perfectionniste que vous êtes, vous exigez cependant de n’utiliser que des polygones réguliers pour votre décoration.

Pour satisfaire vos envies, vous pourrez peut-être opter pour un pavage carré. Après tout, dans carrelage, il y a la racine du mot carré, alors quoi de plus naturel que de disposer régulièrement ces quadrilatères dans votre nouvelle pièce.

Plus original, vous pourrez choisir des motifs hexagonaux. On trouve d’ailleurs ces motifs en observant les ruches ou les colonnes basaltiques des massifs volcaniques.

Colonnes hexagonales de basalte… Pas tout à fait régulières, certes, mais impressionnantes !

Mais les pentagones réguliers dans tout ça ? Eh bien, les malheureux n’ont pas autant de chance, et l’on peut s’en rendre compte rapidement en essayant de les accoler les uns aux autres : de toute évidence, ça ne rentre pas !

Rien à faire Robert, ça ne rentre pas…

Pourtant, vous n’en démordez pas : vous utiliserez des pentagones réguliers coute que coute ! Alors, qu’à cela ne tienne, voyons ce que nous pouvons faire de ces polygones

Le rapport d’or

Pour cela, nous allons utiliser une propriété de notre pentagone : si l’on prend la longueur d’une de ses diagonales – un segment lient deux sommets qui ne sont pas voisins – et qu’on le divise par la longueur d’un côté, on obtient une valeur que l’on appelle nombre d’or, environ égale à 1.618.

Ce nombre, noté φ et parfois appelé « Divine proportion« , possède une caractéristique fort utile à notre affaire de pavage : le multiplier par lui-même revient à lui ajouter 1.

φ x φ = φ + 1

Découpons alors notre pentagone en trois triangles isocèles – qui possèdent deux côtés de longueur égale – comme l’indique l’image suivante :

En observant le triangle central, on remarque que sa base est un côté du pentagone, et que ses deux côtés égaux correspondent à deux diagonales du pentagone. Ainsi, le rapport entre la longueur des grands côtés et la longueur de la base de ce triangle vaut φ. Un triangle qui respecte cette règle s’appelle un triangle d’or.

Inversement, les deux triangles des extrémités ont pour base une diagonale du pentagone et, pour côtés égaux, deux côtés du pentagone. Cette fois, c’est le rapport entre la longueur de la base et celle des deux côtés égaux – soit l’inverse de ce que nous avions précédemment – qui est égal à φ. Un tel triangle s’appelle un triangle d’argent.

Et là, nous allons voir pourquoi le nombre d’or possède ce surnom de Divine proportion. Nous allons accoler un triangle d’or et un triangle d’argent provenant du même pentagone régulier, comme sur la figure plus bas. Nous allons supposer que ce pentagone a un côté de longueur 1 unité.

Ses deux côtés égaux correspondent à la base du triangle d’argent, ou a un côté du triangle d’or : ils ont une longueur de φ. Sa base, en revanche, à une longueur de φ + 1, qui est égal à φ x φ. Ainsi, en faisant le rapport entre les longueurs de la base et de ses côtés égaux, nous obtenons φ x φ / φ. En d’autres termes, nous avons, à partir d’un triangle d’or et d’un triangle d’argent, formé un nouveau triangle d’argent.

Triangles d’or et d’argent, de plus en plus grands…

Prenons alors ce nouveau triangle d’argent, et collons un triangle d’or sur un côté. Cette fois, la base a une longueur de φ, et le côté une longueur de φ x φ comme calculé plus haut. Le rapport entre côté et base est donc de φ : c’est un triangle d’or.

Et nous pouvons continuer ainsi à l’infini, avec ce triangle d’or et le triangle d’argent précédents, nous formons un triangle d’argent. Avec ce nouveau triangle d’argent et le grand triangle d’or, nous formons un nouveau triangle d’or, et ainsi de suite, de proche en proche, nous pouvons couvrir tout le plan.

De proche en proche, nous finirons bien par paver le plan ! #30AnsTangente

Nombre d’or, le retour

Voilà donc une solution pour paver en utilisant des fragments de pentagone, mais combien de triangles nous faudra-t-il pour former nos nouveaux triangles, de manière récursive.

La suite des nombres de triangles correspond à une suite bien connue…

En commençant avec 1 triangle d’or et 1 triangle d’argent, nous avons fait un triangle d’argent composé de 2 triangles. Avec ce nouveau triangle et un triangle d’or, c’est un triangle composé de 3 petits triangles qui a été créé. Puis, il en a fallu 5, puis 8, puis 13…

Les amateurs de mathématiques auront vite reconnu la fameuse suite de Fibonacci, où chaque terme est calculé en faisant la somme des deux termes précédents. Et pour cause : chaque triangle est construit à l’aide des deux étapes précédentes, tout comme la suite ! Pas étonnant donc de la revoir dans nos triangles.

Cela devient encore plus intrigant lorsque l’on compte séparément le nombres de triangles de départ utilisés

Etape 1 2 3 4 5 6 7
Nombre total de triangles 1 1 2 3 5 8 13
Triangles d’or 0 1 1 2 3 5 8
Triangles d’argent 1 0 1 1 2 3 5

On remarque que les nombres de triangle d’or et d’argent utilisés sont des termes consécutifs de cette fameuse suite de Fibonacci. Encore une fois, tout est logique puisque les triangles sont construits grâce aux deux étapes précédentes.

Mais ce qui est intéressant, c’est que plus on progresse, plus le rapport entre le nombre de triangles d’or et le nombre de triangles d’argent tend vers… le nombre d’or, φ, encore lui !

Et cette convergence nous montre que le pavage que nous construisons ne peut pas être périodique, c’est-à-dire qu’il n’existe pas un petit modèle, de taille finie, avec lequel on puisse paver tout le plan rien qu’en le translatant ou en le tournant.

En effet, si c’était le cas, il serait composé d’un certain nombres de triangles d’or O et un certain nombre de triangles d’argent A. Le rapport O/A est ce que l’on appelle un nombre rationnel, une fraction. Or, φ ne peut pas être écrit sous une telle forme : il n’est donc pas possible d’avoir un tel modèle.

Pour plus d’allure

Bon, avouons-le, notre triangle n’est pas très beau. Rassurez-vous, car il existe des constructions bien plus élégantes faites avec ces triangles.

Une première construction consiste à utiliser des « fléchettes » et des « cerfs-volants » qu’on obtient en accolant respectivement deux triangles d’argent ou d’or. Par le même principe que pour le triangle, il est possible de construire alternativement des fléchettes et des cerfs-volants de plus en plus grands, jusqu’à paver le plan.

Cerf-volant (gauche) et fléchettes (droite). Il est possible de former un cerf-volant à partir de deux cerf-volants et deux demi-flechettes. Pour la fléchette, il faut un cerf-colant et deux demi-fléchette.

Et voici une partie du résultat qui peut être obtenu :

Pavage avec fléchettes et cerf-volants

De la même manière, en collant les triangles selon leur base, on obtient des losanges que l’on peut encore une fois construire successivement, jusqu’à recouvrir tout le plan. Autant dire que tout cela a plus d’allure que notre pavage de départ !

Pavage avec des losanges d’or et d’argent

Pour compléter

Publié dans Curiosités et récréation | Tagué , , , , | Laisser un 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