Parmi les énigmes mathématiques, celles qui s’éclairent par un changement inattendu de domaine sont particulièrement intéressantes. En voici une dont j’ignore l’origine exacte mais dont la facture fait penser aux Olympiades internationales de mathématiques. L’énoncé concerne une équation fonctionnelle, le voici :
Trouvez toutes les fonctions f de R dans R telles que f [f (x)] = x² – 1 pour tout x. Il peut sembler naturel de chercher à utiliser une méthode analytique mais cela ne donne rien. En fait, de façon non directement visible, le problème est lié à la signature d’une certaine permutation. Pour montrer le lien, considérons la fonction g du second membre, définie par g (x) = x² – 1 pour tout x. Si la fonction f existe, la fonction composée f o f (définie par f o f (x) = f [f (x)]) vérifie f o f = g. On en déduit que f et g o g commutent, soit : g o g o f. = f o g o g. Cette égalité est liée aux points fixes de g o g ! En effet, si x vérifie g o g (x) = x, en portant ce résultat dans l’équation précédente : (g o g) [f (x)] = f (x) donc f (x) est un point fixe de g o g. Autrement dit, f est une application de l’ensemble des points fixes de g o g dans lui-même. On démontre de plus, en utilisant f o f = g que f restreint à l’ensemble de ces points fixes est une permutation. Les points fixes de g o g. Parmi les points fixes de g o g, on trouve d’abord ceux de g. Ce sont les solutions de l’équation x² – 1 = x que l’on peut écrire x² – x – 1 = 0 d'où deux points fixes a et b faciles à calculer (en fonction de la racine carrée de 5). De même, g o g a pour points fixes, les solutions de l’équation (x² – 1)² – 1 = x qui s’écrit (x² – x – 1) x (x + 1) = 0 d’où les quatre points fixes a, b, c et d où c = –1 et d = 0. La fonction g restreinte à l’ensemble des quatre éléments {a, b, c, d} est la transposition qui échange c et d. La fonction f restreinte au même ensemble est une application dont le carré est une transposition ce qui est impossible.
0 Commentaires
Les courbes elliptiques sont très utiles, à travers les structures de groupe qu’on peut y définir. En particulier, ils permettent de créer une méthode de cryptographie à clef publique analogue à la méthode RSA. Ici, nous nous proposons de le décrire de façon très élémentaire. Une courbe elliptique est une courbe d’équation : y² = x^3 + a x + b où a et b sont des nombres réels. Si a < 0 et 4 a^3 + 27 b² < 0, son allure est donnée ci-dessous. On lui adjoint un point fictif dit point à l’infini que l’on note ici 0. Une construction géométrique permet alors de définir une loi interne sur une telle courbe : On note PQ la droite PQ si P ¹ Q et la tangente en P sinon. Si PQ recoupe la courbe en un point R, on note P + Q le point où la verticale en R la recoupe. Sinon, on pose P + Q = 0. De même, on pose : P + 0 = P. Des calculs algébriques sont nécessaires pour montrer que cette loi munit bien la courbe elliptique d’une loi de groupe. La généralité des calculs Plus précisément, si P et Q sont distincts et ont pour coordonnées (xP, yP) et (xQ, yQ) tels que xQ différent de xP, une équation paramétrique de PQ est Ce point appartient à la courbe elliptique si t est solution d’une équation du troisième degré dont le coefficient de degré 3 est (xP – xQ)^3 et celui de degré 2, 3 xQ (xP – xQ)² – (yP – yQ)². P et Q correspondent aux racines 0 et 1 de cette équation, l’autre (que nous noterons t) est donnée par la somme des racines égale à t + 1 d’un côté et au quotient de (yP – yQ)² –3 xQ (xP – xQ)² par (xP – xQ)^3 de l’autre. On en déduit t puis xR et yR d’abord et les coordonnées (xP+Q, yP+Q) de P +Q sont : En tenant compte de y² = x^3 + a x + b, on trouve : On en déduit une formule valable même si P = Q. Cette formule a de plus le mérite de garder un sens dans un corps quelconque. Nous avons simplement besoin de conserver l’hypothèse 4 a^3 + 27 b² non nul et d’utiliser un corps de caractéristique différente de 2 et de 3.
Structure de groupe À partir de ces formules, on démontre facilement que la loi est commutative, que O est élément neutre, que le symétrique du point P par rapport à l’axe des x est son symétrique pour la loi +. En fait, seule l’associativité est délicate à démontrer, ou plutôt longue et fastidieuse mais on peut la faire avec un logiciel de calcul formel puisqu’il s’agit de démontrer que les deux points (P + Q) + R et P + (Q + R) sont confondus. Chiffrement Les courbes elliptiques sur des corps Z/ N (avec N premier) permettent de définir des méthodes de cryptographie à clef publique analogue au système RSA. L’idée de départ est qu’un texte peut être transformé en une suite de points de la courbe. Cela revient à écrire dans un alphabet ayant autant de signes que la courbe a de points. Notons que le problème sous-jacent n’a rien de simple mais, théoriquement, la question est de transformer un point M de la courbe. La clef secrète est constituée d’un point P de la courbe et d’un entier k. On calcule ensuite P ’ = k P. La clef publique est alors le couple de points (P, P ’). Pour chiffrer un point M, le chiffreur choisit un entier l et transmet le couple (U, V) défini par : U = l P et V = M + l P ’. La connaissance de k suffit pour retrouver M : M = V – k U. Il est facile de voir qu’elle est même nécessaire. Logarithme discret Pour retrouver k connaissant P et P ’, il suffit de savoir résoudre l’équation : P ’ = k P. Ce nombre k est appelé logarithme discret ce qui n’est guère intuitif si on utilise la notation additive ci-dessus. Avec une notation multiplicative de la loi du groupe, cela devient plus habituel puisque l’équation s’écrit alors : P ’ = Pk. Dans le corps des réels, k correspondrait alors au logarithme de base P de P ’ d’où le nom dans le cadre d’un groupe fini. À l’heure actuelle, ce problème est considéré comme très difficile. On estime qu’une clef de 200 bits (valeur de N) pour les courbes elliptiques est plus sûre qu’une clef de 1024 bits pour la méthode RSA. Comme les calculs sur les courbes elliptiques ne sont pas compliqués à réaliser, c’est un gros avantage pour les cartes à puces où on dispose de peu de puissance, et où la taille de la clef influe beaucoup sur les performances. Les inconvénients sont de deux ordres. D’une part, la théorie des fonctions elliptiques est complexe et relativement récente. Il n’est pas exclu que l’on puisse contourner le problème du logarithme discret. D’autre part, la technologie de cryptographie par courbe elliptique a fait l’objet du dépôt de nombreux brevets à travers le monde. Cela pourrait rendre son utilisation coûteuse ! Page 138 de mon livre Toutes les mathématiques du monde, je donne la méthode de Tartaglia sous la forme du poème qu’il avait lui-même écrit : Quand le cube auprès des choses S’égale à quelque nombre discret Trouve en lui deux nombres différents Alors tu prendras pour habitude Que leur produit soit toujours égal Au tiers cubé des choses exactement Je l’applique ensuite pour résoudre l’équation de Bombelli : … sans aller dans les détails de calcul pour ne pas alourdir la lecture. Les voici pour ceux qui aiment aller au bout des calculs. Suivre les conseils du poème Comme Tartaglia le recommande dans son poème (trouve en lui deux nombres différents), on pose d’abord x = u + v ce qui donne, en utilisant la formule du binôme : Le conseil a priori étrange de Tartaglia (leur produit égal au tiers cubé des choses) signifie qu’il convient de poser uv = 5 (15 divisé par 3), ce qui simplifie l’équation en : En posant U et V les cubes de u et v, on arrive à un système classique depuis Diophante, où somme S et produit P de deux nombres (U et V ici) sont donnés (4 et 125 ici). U et V sont alors solutions de l’équation du second degré X² – S X + P = 0 soit X² – 4 X + 125 = 0. Cette dernière équation se simplifie en considérant : (X – 2)² = X² – 4 X + 4. L’équation se transforme en : (X – 2)² = –121.
Une idée folle Bombelli eut l’idée folle, et géniale, de continuer comme si –121 avait une racine carrée. Il la nota seulement en introduisant une racine carrée de – 1, que nous notons aujourd’hui i, et obtint donc U et V en fonction de ce nombre : U = 2 + 11 i et V = 2 – 11i (ou l’inverse ce qui ne change rien, vu la symétrie entre u et v). On cherche alors u sous la forme a + ib, a et b étant des nombres réels. Comme i² = – 1, en développant (a + ib) au cube, a et b sont solutions du système : a (a² – 3b²) = 2 et b (3a² – b²) = 11. On trouve facilement une solution particulière, en la cherchant entière. Puisque 2 et 11 sont des nombres premiers : a = 2 et b = 1. On trouve donc : u = 2 + i et v = 2 – i. On en déduit que x = 4 est solution ce qui est facile à vérifier. Les nombres imaginaires Ainsi, un calcul a priori absurde sur des nombres impossibles, comme on les a d’abord nommés, permettait d’obtenir un résultat exact ! En fait, de nouveaux nombres étaient nés sans que l’on comprenne bien ce qu’ils pouvaient signifier. Ils donnaient des résultats corrects que l’on pouvait vérifier, c’est pourquoi ils furent admis dans la grande famille des nombres. Descartes les nomma « imaginaires » pour les distinguer des autres qui, à cette occasion, devinrent les nombres réels. Ces nombres ne prirent une réalité que beaucoup plus tard sous le nom de nombres complexes. Un concept était né de pures manipulations algébriques. |
AuteurJe tiens un blog de vulgarisation mathématique sur Futura où je réduis les côtés techniques au maximum. Ce blog est destiné à le compléter pour ceux qui désirent aller plus loin. ArchivesCatégories |
Site créé en collaboration avec Weebly et géré par Webmasterstudio