Kilomaths.com

Partage de secret

07/07/2010 Tukikun Aucun commentaire

Supposons que le PDG d’une grande compagnie de soda veuille garder secrète la recette qui a fait la fortune de l’entreprise. Il l’enferme donc dans un coffre fort blindé, qui s’ouvre à l’aide d’une certaine clé (qu’il garde secrète). Cette solution est très sécuritaire dans le sens où seul le PDG peut accéder au secret. Mais elle revêt un gros défaut : si le PDG perd cette clé, ou vient à décéder dans un accident, la clé est perdue et personne ne peut jamais accéder à la recette, entraînant inévitablement la déroute de la multinationale.

Une des solutions est de donner des copies de cette clé secrète à des collaborateurs au travail. Mais répliquer la clé augmente les chances des espions de l’obtenir et de rapporter la recette à l’entreprise concurrente. Le PDG est bien conscient qu’il ne peut pas faire entièrement confiance à un de ses 5 subordonnés. Il veut donc mettre en place un schéma où tout groupe contenant au moins 3 de ses subordonnés puisse ouvrir le coffre alors que tout groupe contenant strictement moins de 3 subordonnés ne puisse rien savoir sur la clé.
Une solution qui consisterait à donner des bouts du secret aux subordonnés de manière à ce qu’ensemble ils puissent le reconstruire ne convient pas parce qu’ils connaîtraient alors partiellement la clé secrète.

Ce problème peut-être résolu par la mise en place d’un schéma de partage de secret.

Le partage de secret avec seuil

Notons $2\leq t<n$ des entiers. Notre but est de partager une clé secrète $K$ entre un ensemble de $n$ personnes $\mathcal P = \{P_1, \ldots, P_n\}$ de telle manière que toute coalition de $t$ ou plus de ces personnes puisse calculer $K$ facilement, et que toute coalition de $t-1$ ou moins de ces personnes ne puisse rien déterminer sur la valeur de $K$ , autrement dit que toutes les valeurs de $K$ possibles soient équiprobables. Un tel schéma est appelé un schéma au seuil $(t,n)$ . Dans l’exemple introductif, le PDG cherche un schéma au seuil $(3,5)$ .

La valeur du secret est choisie par un participant spécial $D$ (le dealer) (que l’on suppose bien évidemment ne pas faire partie de $\mathcal P$ ). Le dealer va donner à chaque participant une clé de partage. Cette distribution sera secrète bien entendu, pour qu’aucun des participants ne connaissent les clés de partage des autres participants.

Le problème de construire un tel schéma a été résolu indépendamment par Sharmir [1] et Blakley [2] en 1979.

Schéma de Shamir

Commençons par présenter le schéma de Shamir, qui repose sur l’interpolation polynômiale.

Le dealer veut partager la clé secrète $K\in \mathbf F_q$ où $q\geq n+1$ est la puissance d’un nombre premier (on peut prendre $q=p$ premier et raisonner dans $\mathbf F_p$ bien évidemment). Il choisit de manière aléatoire $n$ éléments distincts de $\mathbf F_q$ que l’on note $x_1, \ldots, x_n$ . Ces éléemnts ne sont pas les clés de partages secrètes, ce sont des clés publiques : chaque $P_i$ reçoit la clé $x_i$ . Dans l’exemple du PDG, on pourrait dire par exemple que $x_i$ représente l’ordre d’arrivée de l’employé dans l’entreprise. Ensuite, il réalise les étapes suivantes :

Il choisit secrètement et aléatoirement $t-1$ éléments de $\mathbf F_q$ notés $a_1, \ldots, a_{t-1}$ .
Pour tout $1\leq i\leq n$ , le dealer calcule $y_i=a(x_i)$ où
$a(X) = K+\sum_{i=1}^{t-1}a_jX^j.$
Pour tout $1\leq i\leq n$ , le dealer donne secrètement la clé de partage $y_i$ à $P_i$

Regardons comment un groupe $B=\left\{P_{i_1}, \ldots, P_{i_t}\right\}$ de $t$ personnes (avec leur clé publique $x_i$ ) peut retrouver les coefficients secrets du polynôme $a(X)$ par interpolation, et ainsi retrouver $K=a(0)$ . Comme $y_{i_k} = a(x_{i_k})$ pour tout $0\leq k\leq t$ , le groupe $B$ obtient $t$ équations linéaires en les $t$ inconnues $K, a_1, \ldots, a_{t-1}$ . Ainsi, le système obtenu par $B$ peut-être écrit sous la forme

$\begin{pmatrix}1& x_{i_1}& x_{i_1}^2& \cdots& x_{i_1}^{t-1}\\1& x_{i_2}& x_{i_2}^2& \cdots& x_{i_2}^{t-1}\\\vdots& \vdots & \vdots & & \vdots\\1& x_{i_t}& x_{i_t}^2& \cdots& x_{i_t}^{t-1}\\\end{pmatrix}\begin{pmatrix}K\\a_1\\\vdots\\a_{t-1}\end{pmatrix} = \begin{pmatrix}y_{i_1}\\y_{i_2}\\\vdots\\y_{i_t}\end{pmatrix}.$

Or, la matrice $A$ des coefficients $x_i$ est appelée matrice de Vandermonde et son déterminant vaut $\det(A) = \prod_{1\leq k<j\leq t}\left(x_{i_j}-x_{i_k}\right)\neq 0$ . Comme il est non nul (par choix des $x_i$ ), le système admet une unique solution sur $\mathbf F_q$ , et $K$ peut-être retrouvé.

Supposons maintenant que $t-1$ des $n$ clés de partages secrètes sont révélées à un ennemi. Pour chaque candidat $K'\in \mathbf F_q$ pour le secret, l'ennemi peut construire un et un unique polynôme $a'(X)$ de degré $t-1$ tel que $a'(0)=K'$ et $a'(x_i)=y_i$ pour les $t-1$ clés connues. Par construction, ces $q$ possibles polynômes sont équiprobables, en conséquence de quoi l'espion ne peut rien déduire sur la valeur de la clé secrète $K$ .

Bien entendu, il y a une méthode alternative basée sur la formule de l'interpolation de Lagrange. La formule est la suivante :

$a(X) = \sum_{j=1}^t y_{i_j} \prod_{\substack{1\leq k\leq t\\k\neq j}}\frac{X-x_{i_k}}{x_{i_j}-x_{i_k}}.$

Étant donné qu’un groupe recherche la valeur du secret $K=a(0)$ , ils peuvent calculer

$K = \sum_{j=1}^{t}y_{i_j}b_j, \qquad \text{avec} \quad b_j = \prod_{\substack{1\leq k\leq t\\k\neq j}}\frac{x_{i_k}}{x_{i_k}-x_{i_j}}.$

Remarquons que les valeurs $b_j$ ne dépendent que des $x_i$ et peuvent-être pré-calculées.

Un exemple concret

Donnons un petit exemple concret pour soulager notre PDG qui a vraiment peur de faire un infarctus qui perdrait à tout jamais la recette ! Supposons que $q=17$ et que les coordonnées publiques sont $x_i = i$ pour tout $1\leq i\leq 5$ . Supposons maintenant que les collaborateurs $P_1$ , $P_3$ et $P_5$ veuillent retrouver le secret. Ils mettent en commun leurs clés de partages secrètes qui sont respectivement $8$ , $10$ et $11$ . Comme $a(X) = K+a_1X+a_2X^2$ , ils obtiennent le système d’équation suivant :

$\left\{\begin{array}{lll}K+a_1+a_2 &=&8\\K+3a_1+9a_2&=&10\\K+5a_1+8a_2&=&11\end{array}\right.$

Ce système admet une unique solution dans $\mathbf F_{17}=\mathbf Z/17\mathbf Z$ : $K=13$ , $a_1=10$ et $a_2=2$ . Le secret est donc $K=13$ !

Schéma de Blakley

Donnons un autre exemple : le schéma de Blakley basé sur la géométrie des hyperplans sur les corps finis. Le secret est un point d’un espace $t$ -dimensionnel, et les $n$ clés de partages secrètes sont des hyperplans affines passant par ce point. Un hyperplan dans un espace $t$ -dimensionnel à coordonnées dans un corps $\mathbf F$ peut être décrit par une équation de la forme suivante :

$a_1x_1 + a_2x_2 + \cdots + a_tx_t = y.$

Le point d’intersection est obtenu en trouvant l’intersection d’un ensemble quelconque de $t$ de ces hyperplans. Par exemple, le secret peut être la première coordonnée du point d’intersection.

Disons que $\mathbf F = \mathbf F_q$ est le corps sur lequel on travaille. Le dealer génère un point $x$ dans $\mathbf F_q^t$ , où la première coordonnée $x_1$ est la clé secrète et les autres coordonnées sont choisies aléatoirement dans $\mathbf F_q$ . Le $i$ ème participant recevra comme clé de partage secrète l’hyperplan sur $\mathbf F_q$ d’équation

$a_{i,1}x_1+a_{i,2}x_2+\cdots+a_{i,t}x_t=y_i.$

Pour obtenir un schéma au seuil $(t, n)$ , il y aura $n$ équations d’hyperplan, et on obtient alors un système linéaire $n\times t$ : $Ax=y$ .

Le dealer donne en pratique la clé de partage secrète $y_i$ ainsi que les coordonnées (qui peuvent être publiques) $a_{i,1}, \ldots, a_{i,t}$ au participant $P_i$ . un choix judicieux pour la matrice $A$ est de faire en sorte que ses lignes soient les lignes d’une matrice de Vandermonde pour se ramener à une situation similaire à celle du schéma de Shamir.

Pour aller plus loin…

Bien entendu, ceci n’est qu’une introduction sommaire à un domaine toujours en pleine expansion en cryptologie. On pourra trouver d’autres schémas basés sur la géométrie, sur les graphes, sur le théorème des restes chinois… Une excellente introduction au sujet est l’article [3].

Pour les plus intrépides d’entre vous, remarquez que jusquà présent nous avons travaillé sur des corps, s’autorisant allégrement la possibilité d’inverser pour retrouver le secret si nécessaire. Un sujet intéressant est de vouloir construire des schémas valables sur n’importe quel groupe abélien (sans connaître le groupe, c’est-à-dire un schéma en boîte noire), qui ont fait l’objet de deux articles récents [4] et [5].

Références

[1] A. Shamir – « How to share a secret », Communications of the ACM 22 (1979), no. 11, p. 612 – 613.
[2] G. R. Blakley – « Safeguarding cryptographic keys », AFIPS Conference Proceedings 48 (1979), p. 313 – 317.
[3] D. R. Stinson – « An explication of secret sharing schemes », Designs, Codes and Cryptography 2 (1992), no. 4, p. 357 – 390.
[4] R. Cramer & S. Fehr – « Optimal black-box secret sharing over arbitrary Abelian groups », Advances in Cryptology – CRYPTO’02 (2002), p. 272 – 287.
[5] R. Cramer, S. Fehr & M. Stam – « Black-box secret sharing from primitive sets in algebraic number fields », Advances in Cryptology – CRYPTO 2005, Springer, 2005, p. 344-360.

Categories: Maths difficiles, Vulgarisation Tags: Blakley, cryptologie, interpolation, Lagrange, matrice, partage de secret, polynôme, secret, Shamir, Vandermonde

Rapporteurs de Golomb et algorithmes génétiques

25/05/2010 Tukikun un commentaire

Dans le cadre du T.I.P.E de seconde année de classe préparatoire aux Grandes Écoles, j’ai travaillé sur la recherche de rapporteurs de Golomb via les algorithmes génétiques ; une idée originale développée par André Narbonne sur son site internet (apparemment plus disponible).

Les algorithmes génétiques font parti de la famille des algorithmes évolutifs, et s’inspirent de l’évolution biologique telle que décrite par Darwin. Leur principale utilisation est la résolution de problèmes concrets d’optimisation, trop complexes pour être résolus de façon exhaustive, tel le problème du voyageur de commerce, où l’on cherche le meilleur itinéraire (c’est-à-dire le plus court) pour relier un nombre fini de villes.

Dans cet article, nous étudierons la possibilité d’appliquer les algorithmes génétiques pour découvrir des rapporteurs de Golomb.

Qu’est qu’un rapporteur de Golomb ?

Le mathématicien Solomon W. Golomb présenta en premier lieu « la règle de Golomb » qui est une règle mesurant plus de longueurs (discrètes) que le nombre de marques qu’elle contient. De plus, la même distance n’est pas mesurée deux fois.

Un exemple simple de cette règle est celle constituée des marques 0; 1; 4; 6 qui permet de mesurer les longueurs 1; 2; 3; 4; 5 et 6 une et une seule fois entre deux marques de la règle.

C’est en partant de cet exemple simple que la question s’est posée pour les rapporteurs : est-il possible de faire un rapporteur avec le moins de marque possible qui mesure les angles de 1 à 360 degrés ? Un rapide calcul montre que la limite minimale théorique est de 20 marques : en effet, avec $n$ marques, on peut mesurer $n(n-1)$ angles. Pour 19 marques, on mesure ainsi au plus 342 angles, et au plus 380 pour 20 marques.

La solution de l’algorithme génétique semble adaptée à ce problème. En effet, si pour 20 marques, l’on voulait tester toutes les possibilités, afin de trouver celle qui permet la mesure de 180 angles (si tant est que ce soit possible), avec les marques 0 et 1 fixées (une simple rotation nous y ramène), il faudrait près de $10^{45}$ opérations pour construire les rapporteurs, et d’avantage encore ( $10^{90}$ ) pour compter le nombre d’angles qu’ils mesurent.

Plan de l’algorithme

Génération : L’algorithme génétique présenté sur l’organigramme débute avec une génération de $N$ rapporteurs (entre une centaine et quelques milliers par exemple), c’est-à-dire des tableaux de taille $n$ (nombre de marques désiré), contenant des angles compris entre 0 et 359, triés par ordre croissant. Le tri de ces tableaux est une opération relativement coûteuse (utilisation du tri rapide), mais il n’est effectué qu’une fois au début de l’algorithme.

On calcule ensuite pour chaque rapporteur le nombre d’angles qu’il mesure, sachant que l’on cherche à en obtenir un mesurant tous les angles de 1 à 360 degrés.

Puis on répète le processus suivant un nombre fini de fois : (c’est-à-dire de générations)

Calculs de la moyenne, du minimum, et du maximum d’angles mesurés, ce qui servira pour la sélection, et pour observer l’évolution de la population.
Évaluation : On attribue à chaque rapporteur une probabilité de survie, dépendant du nombre d’angles qu’il mesure. Plus un rapporteur mesurera d’angles, plus il aura de chance de survivre. Les différentes fonctions d’évaluation seront décrites et comparées plus loin.
Sélection : Si un rapporteur « survit », on le conserve pour la génération suivante. Sinon, on choisit au hasard deux parents, que l’on croise (Croisement) pour obtenir un « enfant », dont on compte les angles.

On obtient ainsi une nouvelle génération de même taille, sur laquelle on effectue éventuellement des mutations, avant de recommencer le processus.

Evaluation

Différents types de fonctions d’évaluation ont été étudiés afin d’obtenir une vitesse de convergence optimale, ainsi qu’un échantillonnage optimal. Le but étant de sélectionner les meilleurs individus, tout en
laissant une part de « moins bons » individus pour conserver une certaine diversité et variabilité. On évite ainsi la convergence rapide vers un individu optimal localement mais non solution au problème.

Rang Affine

Le type affine fait correspondre à chaque individu une probabilité de survie qui est fonction affine du nombre d’angle $m$ qu’il mesure, c’est-à-dire de la forme $am + b$ , où $a$ et $b$ sont à déterminer arbitrairement.

Cependant les meilleurs résultats ont été obtenus en utilisant des coefficients variables dépendant des variables moyenne, minimum et maximum du nombre d’angles mesurés.

Le type exponentiel fait correspondre à chaque individu une probabilité de survie qui est fonction exponentielle du nombre d’angle $m$ qu’il mesure, c’est-à-dire de la forme $e^{am +b}$ , où $a$ et $b$ sont à déterminer arbitrairement. En agissant sur les coefficients, on peut accentuer ou diminuer la courbure selon la méthode de sélection voulue.

Rang Exponentiel

Une autre méthode, qui a produit de meilleurs résultats, est d’attribuer à chaque individu son rang (fonction du nombre d’angles mesurés), et de se servir de celui-ci plutôt que du nombre d’angles mesurés pour l’évaluation. Un tri par dénombrement a été utilisé pour déterminer le rang de chaque individu. L’évaluation peut ici aussi être fonction affine ou exponentielle du rang. Une comparaison entre ces deux méthodes sur 500 générations (statistiques sur plusieurs populations) révèle une convergence plus rapide et pas moins optimale pour la méthode affine.

Sélection

Deux méthodes ont été envisagées : soit construire la nouvelle génération uniquement à partir d’ « enfants » obtenus par croisement (cf. partie Croisement) de 2 parents, soit remplacer uniquement les parents non sélectionnés, et conserver ceux qui ont « survécu ». C’est cette dernière méthode qui a été retenue.

L’algorithme initial ne gardait pas les meilleurs individus, ce qui a été résolu par la suite. C’est ce que l’on appelle la méthode élitiste, qui a montré ses preuves dans beaucoup d’études faites sur les algorithmes génétiques, y compris sur cet exemple.

Croisement

Le premier croisement étudié était un croisement très simple : les tableaux de chaque parent étaient parcourus simultanément et, une des deux valeurs choisie aléatoirement (sauf si elle a déjà été choisie)
constituait la nouvelle valeur pour l’enfant créé. Cependant, cette méthode ne conservait pas la structure des parents, et était de ce fait trop aléatoire.

Le second croisement fut un croisement à 1 point : l’ordinateur choisissait un angle au hasard et découpait les parents pour fabriquer deux enfants, l’enfant 1 ayant la première moitié du parent 1 et la seconde du parent 2, et inversement pour l’enfant 2. A la vue de divers ouvrages sur les algorithmes génétiques, il nous est apparu que le croisement à deux points était plus avantageux (même principe qu’à un point mais avec un découpage en trois parties). En effet, il permet plus de combinaisons possibles à partir de mêmes parents, et ainsi permet une plus grande variabilité des individus. Ce fut donc le troisième et dernier croisement testé, et celui gardé pour l’algorithme final. Le choix entre les deux enfants est aléatoire, afin de ne pas nuire à la diversité en choisissant systématiquement le meilleur enfant.

Mutation

Là également diverses méthodes ont été essayées, mais elles n’ont pas donné de résultats significativement différents. Le principe est le même à chaque fois : on parcourt la population, on génère un nombre décimal aléatoirement entre 0 et 100, et s’il est inférieur à un coefficient de mutation défini au début de l’algorithme, on mute l’individu. La première mutation essayée était la modification d’un angle choisi au hasard en lui rajoutant plus ou moins 1. La seconde était le remplacement d’un angle au hasard par un nouvel angle choisi aléatoirement entre le précédent et le suivant.

La troisième mutation testée, et celle qui a été conservée, permet de jouer sur chaque angle de chaque individu, définissant le coefficient de mutation non plus pour un individu mais pour chaque angle. Ceci complique l’algorithme, mais a permis d’avantage de résultats pour 25 marques.

De la même façon pour le croisement, il est possible d’utiliser une méthode élitiste, c’est-à-dire de conserver l’individu obtenu après mutation seulement s’il est meilleur que l’original.
Celle-ci semble diminuer encore une fois la diversité, mais la comparaison ci-contre permet tout de même de valider celle-ci, et de décider du meilleur coefficient de mutation à choisir.
Un minimum de mutation est nécessaire pour améliorer et diversifier les individus. Mais s’il est trop élevé, chaque individu a une trop grande probabilité d’être muté, et de ce fait les résultats deviennent trop aléatoires.

Autre piste intéressante

Comme suggéré par André Nabonne, sur le site Internet sur lequel il a effectué un travail semblable, il est possible de rechercher les meilleurs éléments pour un nombre de marques moins important et le compléter ensuite pour obtenir un rapporteur qui mesure 360 angles avec 1 à 2 marques supplémentaires. Cependant ce n’est pas la méthode qu’il lui a permis de battre le record précédemment détenu par J. Cottereau avec 24 marques, en obtenant des rapporteurs de 23, et même de 22 marques.

Oui c’est joli le blabla… Mais on peut voir un vrai rapporteur de Golomb ?

– Pour 27 marques : 0, 8, 14, 40, 41, 42, 45, 58, 75, 99, 146, 151, 153, 175, 179, 180, 193, 218, 241, 276, 285, 300, 321, 323, 331, 348, 349
– Pour 26 marques : 0, 5, 49, 51, 65, 91, 92, 97, 107, 115, 136, 144, 148, 176, 180, 198, 200, 207, 210, 211, 219, 270, 287, 305, 327, 330
– Pour 25 marques : 0, 22, 41, 42, 44, 56, 60, 106, 132, 137, 189, 191, 219, 235, 236, 244, 246, 259, 310, 315, 322, 343, 347, 353

Categories: Divers, Réflexions, Vulgarisation Tags: algorithme, algorithme génétique, Golomb, prépa, rapporteurs, TIPE

Le théorème de Jordan

13/12/2009 Valvino un commentaire

Prenez une feuille de papier, et un stylo. Tracez une ligne, avec pour conditions

ne pas lever le stylo;
ne pas repasser par dessus la ligne;
refermer la ligne sur elle-même à la fin.

Une ligne respectant les conditions.

Le théorème de Jordan vous dit alors que vous avez découpé votre feuille en deux parties d’un seul bloc, avec une partie finie et l’autre infinie (si on considère que le papier pourrait être aussi grand que l’on veut). Et là bien sûr vous vous dites qu’il ne faut pas sortir de Polytechnique pour établir des résultats aussi évidents… Hé bien, en dépit de son apparente simplicité, ce théorème est très difficile à démontrer. Tout réside dans le fait qu’il existe des lignes dans le plan très vicieuses…

Commençons par énoncer rigoureusement le théorème. Tout d’abord, on définit une courbe (c’est-à-dire une ligne) comme une fonction $f$ qui part de l’intervalle $[0,1]$ et qui va dans le plan. D’une certaine manière, $[0,1]$ peut être vu comme le temps (0 le début du tracé, 1 la fin) et $f(t)$ le point tracé exactement à l’instant $t$ . On exige que cette fonction soit continue (la condition de ne pas lever le stylo), ainsi la courbe est « en un seul morceau ». De plus, on veut que la courbe se referme sur elle-même à la fin, donc on exige $f(0)=f(1)$ . Enfin, il ne faut pas que la courbe repasse sur elle-même, on veut donc que $f(t_1) \neq f(t_2)$ à deux instants $t_1$ et $t_2$ qui ne sont pas exactement 0 et 1. On a donc une condition d’injectivité de la courbe (la courbe doit être injective sur $[0,1[$ et $]0,1]$ ). Les courbes ainsi définies portent le doux nom de courbes de Jordan.

Comment formaliser le concept d’être « d’un seul bloc »? On dit qu’une partie du plan est connexe (c’est-à-dire d’un seul bloc) si on peut toujours passer d’un point de cette partie à un autre par une courbe continue.

La partie A est connexe, alors que B ne l'est pas.

Rappelons que le complémentaire d’une partie du plan est tout simplement la partie du plan constituée des points qui ne sont pas dans la première. Deux parties du plan sont dites disjointes si elles n’ont pas de points en commun. Enfin, une partie du plan est dite bornée quand on peut l’inclure dans un disque de rayon fini.

On peut alors énoncer correctement le théorème de Jordan :

Le complémentaire d’une courbe de Jordan est constitué de deux parties connexes qui sont disjointes. L’une est bornée, et l’autre non.

Pourquoi ce théorème est-il si difficile à démontrer? Tout simplement parce qu’il existe des courbes de Jordan très vicieuses. Comme exemple, prenons une courbe de Jordan de type fractale appelée flocon de von Koch. Sans rentrer dans les détails, c’est une courbe obtenue en itérant une infinité de fois le procédé décrit dans l’animation suivante :

Les premières étapes de la construction du flocon de von Koch.

Le problème de ce genre de courbe est qu’il est difficile de savoir si deux points peuvent être reliés par une courbe continue qui ne passe pas par dessus le flocon à cause des innombrables radicelles que forme la courbe. C’est ce qui fait la difficulté de ce théorème!

Pour plus d’informations, vous pouvez consulter le très bon article wikipédia sur le sujet.

Categories: Vulgarisation Tags: connexité, flocon, fractale, Jordan, plan, théorème, topologie, von Koch

La topologie, qu’est-ce que c’est?

03/11/2009 Valvino 3 commentaires

La topologie est la branche des mathématiques qui étudie des concepts comme la distance, la continuité, la notion de limite.

Prenons comme point de départ la notion de distance. À priori, rien de bien profond, cela ne dépasse pas le stade de mesurer avec une règle la distance qui sépare deux points. Cependant, les mathématiques s’autorisent à parler d’autres distances. Et elles ne sortent pas que de leur imaginaire tordu!

Tout le monde s’accorde à dire que sa maison est proche de celle de son voisin. Mais mettons-nous dans la peau d’un employé de France Telecom (pas trop sinon cela risque de mal tourner…). De son point de vue (les télécommunications), la maison de monsieur X peut être assez distante de celle de madame Y, alors qu’ils sont voisins! En effet, si X téléphone à Y pour convenir d’un rendez-vous galant, le signal passera par des centaines de kilomètres de câbles avant d’arriver. Supposons que X et Y habitent à Toulouse et que le signal passe par Paris. Alors on peut considérer du point de vue de France Telecom que la distance entre la maison de X et la mienne (j’habite en région parisienne) est plus petite que la distance entre la maison de X et celle de Y, qui sont pourtant voisins, car le signal met moins de temps pour aller de chez X à chez moi que de chez X à chez Y.

Cet exemple montre qu’il est pertinent de considérer d’autres notions de distance. À titre d’exemple, il existe une distance appelée distance SNCF sur le plan qui consiste à dire que la distance entre deux points P et Q du plan est égale à la distance usuelle si les deux points sont alignés avec l’origine O, et sinon égale à la somme de la distance entre P et O et la distance entre Q et O. Elle porte ce nom en référence au fait qu’il est souvent plus rapide de passer par une correspondance à Paris pour rejoindre deux villes de province par le train.

La distance entre P et Q est plus grande que celle entre P et R, au sens de la distance SNCF.

Citons une dernière distance sur le plan. Prenons le jeu d’échec. La tour ne se déplace qu’en ligne droite. La distance entre deux cases est donc la somme de la distance à parcourir horizontalement et de la distance à parcourir verticalement.

La distance entre la tour et la case marquée d'une croix rouge est de 9 cases.

La distance à parcourir pour la tour afin de rejoindre la croix rouge est de 9 cases.

Les mathématiques ont formalisé la notion de distance, afin de mieux les comprendre. On procède de la manière suivante : prenons un ensemble $X$ de points (par exemples le plan ou l’espace). La distance entre deux points $x$ et $y$ de $X$ est un nombre positif noté $d(x,y)$ qui doit vérifier les trois propriétés suivantes :

$d(x,y)=d(y,x)$ (la distance entre un premier point et un second est la même que la distance entre le second et le premier);
si $d(x,y)=0$ alors $x=y$ et réciproquement (si la distance entre deux points est nulle, alors ces deux points sont les mêmes, et réciproquement);
$d(x,y) \leq d(x,z)+d(z,y)$ (la distance entre deux points est toujours plus petite que la somme de la distance du premier point à un troisième et de la distance du troisième au deuxième).

La distance des échecs vue plus haut pourrait alors se formaliser en disant que la distance entre deux points du plan $X=(x_1,x_2)$ et $Y=(y_1,y_2)$ est

$d(X,Y)=|y_1-x_1|+|y_2-x_2|.$

Le lecteur consciencieux pourra démontrer que les trois propriétés sont bien vérifiées. On peut remarquer une chose amusante au sujet de cette distance. Si on définit le cercle de rayon 1 comme l’ensemble des points dont la distance au centre est 1, alors ce cercle est… un carré!

Une fois cette notion de distance établie, la topologie s’intéresse à des concepts comme la notion de voisinage : comme définir proprement la notion d’être proche au sens d’une distance? Ou encore la notion de continuité : un phénomène entre deux ensembles muni d’une distance (pas nécessairement les mêmes) est dit continu si les conséquences varient peu (au sens de la distance considérée sur le deuxième ensemble)) lorsque les causes sont proches (au sens de la distance considérée sur le premier ensemble).

Categories: Vulgarisation Tags: continuité, distance, point, sncf, topologie, voisinage

Les nombres complexes existent-ils ?

15/09/2009 Valvino 5 commentaires

Bon nombre d’élèves de terminale S se sont posés la question quand le prof a écrit au tableau l’égalité $i^2=-1$ : « mais les nombres complexes, ça n’existe pas! ».

Ce qu’il faut bien avoir en tête, c’est que les objets mathématiques sont construits, ils ne sortent pas de nulle part. La règle du jeu, c’est que l’on peut faire tout ce qu’on veut, du moment que la logique est respectée. Par exemple, les étudiants de premier cycle de mathématiques voient comment construire les ensembles des entiers relatifs, des rationnels, des nombres réels, ensembles dont personne ne conteste l’existence. Pourquoi ne pas construire d’autres ensembles que nous facilitent la vie? Certes, c’est souvent très abstrait : un réel peut être défini comme une classe d’équivalence de suite de Cauchy rationnelles modulo la relation d’équivalence « la différence tend vers zéro à l’infini« …

Ce qui est intéressant, c’est que bien que les complexes soient a priori les objets les moins intuitifs que les élèves du lycée rencontrent, la construction de l’ensemble des nombres complexes est beaucoup plus simple que celles des autres ensembles de nombres. Je propose de l’exposer dans les grandes lignes ici.

Un nombre complexe est défini par sa partie réelle et sa partie imaginaire. On a donc envie de dire qu’un nombre complexe, c’est plus ou moins un couple de réels. C’est une bonne piste. On définit donc un nombre complexe $z$ comme un couple de nombre réels : $z=(a,b)$ .

Après, on veut additionner deux nombres complexes. Ça tombe bien, on dispose d’une addition naturelle sur les couples de nombres réels : on additionne coordonnée par coordonnées On pose donc
$z_1+z_2=(a_1,b_1)+(a_2,b_2)=(a_1+a_2,b_1+b_2).$
Maintenant, on veut définir une multiplication. On pose alors
$z_1 \times z_2 =(a_1,b_1)\times (a_2,b_2)=(a_1 a_2-b_1b_2,a_1b_2+b_1a_2).$
Certes ça parait sortir de nulle part, mais en fait ces formules ont été établies empiriquement en faisant des calculs, et ici le but est de faire une justification formelle. On pose donc la multiplication comme on a envie qu’elle soit sur les nombres complexes.

Ensuite, il suffit de remarquer que
$(0,1)^2=(0,1)\times (0,1)=(0\times 0- 1 \times 1, 0\times 1+1 \times 0)=(-1,0).$
Cela devient intéressant! On a donc envie de poser $i=(0,1)$ .

Je passe sur les détails, mais on identifie le nombre complexe $(a,0)$ avec le nombre réel $a$ , et on montre alors que tout nombre complexe s’écrit de manière unique comme $z=a+ib$ avec $a,b$ des nombres réels. Et on montre enfin que les nombres complexes ont les bonnes propriétés (ils sont inversibles, les lois définies plus haut sont compatibles avec celles sur les nombres réels, etc…).

Voilà donc comment construire facilement les nombres complexes. Je profite de cet article pour dire à quel point je regrette que ce genre de chose ne soit plus au programme du lycée. Cela ne me semble pas très difficile, les cours de maths feraient moins recettes miracles de cuisine, et surtout cela soulignerait la vraie nature des maths : ce n’est pas que du calcul, mais surtout l’étude rigoureuse d’objets construit logiquement.

Pour approfondir, je vous conseille cette page où il y a des réflexions sur la construction des mathématiques, et la page Wikipédia sur la construction des nombres complexes.

Categories: Vulgarisation Tags: construction, corps, lycée, nombres complexes

Anciennes entrées

Archive