Archives par mot-clé : puissance

Les comptes de la crypte

Légende d’un dialogue
L’anthropologue parle/écrit en noir (Stéphanie Messal)
Le mathématicien parle/écrit en gris (Florian Caullery)

Ambiance sonore

Conseils préalables pour fouiller une crypte

A l’occasion de la conférence YACC 20121 qui se déroulait du 24 au 28 septembre sur les îles de Porquerolles, Florian le mathématicien était convié à exposer son travail de recherche en cours : « A new step toward the classification of APN functions »2.

Pour se faire, il a réalisé un Beamer qui est ce qu’on pourrait définir comme l’équivalent d’un PowerPoint mais pour les mathématiques. A la veille de son départ, Florian se décide (enfin) à m’offrir la primeur de son discours. Je relève plusieurs incohérences de présentation : un manque de linéarité, plusieurs allers et retours consécutifs entre les slides qui parasitent au final grandement la compréhension d’un propos qui me semble déjà suffisamment incompréhensible comme ça ! N’étant pas une mathématicienne, je me suis surtout concentrée sur sa présentation, tant dans son propos oral que dans son illustration visuelle. Nous avons donc décidé de reprendre point par point les quelques incohérences du discours pour le rendre plus fluide et plus agréable à entendre et à voir.

Au départ, je voulais surtout me focaliser sur le contenant : la mise en page d’un Beamer (tout comme d’un PowerPoint) est importante si on veut le rendre attrayant et pertinant. Il ne doit pas être le discours oral retranscrit dans son intégralité mais un élément visuel qui reprend les points forts, les notions clés, les définitions spécifiques et bien sûr la structure du discours point par point. Choisir la couleur et recadrer les éléments visuels tels que tableaux, puces, titres fut facile mais réorganiser le contenu prit des proportions inattendues. Comment choisir les mots et phrases clés à conserver sans saisir le sens du propos ? Pour Florian, tout était évident et écrit tel qu’il l’exposait. Mais quand il a fallu déterminer quelles notions devaient rester, comment mettre en lumière un terme plus qu’un autre, nous venions alors de rencontrer une difficulté majeure : comment se comprendre sur nos attentes alors que nous n’utilisions pas le même langage bien que nous communiquions dans une même langue ? Nous parlons tous les deux le français et l’anglais, et la structure des phrases est aisée à saisir pour l’un comme pour l’autre mais… de quoi parle-t-il ? Dès que des termes propres aux mathématiques apparaissaient à l’écran et encore pire quelques savantes formules, ma capacité à comprendre le fondement du propos s’évaporait. C’est tout un pan de vocabulaire spécifique aux mathématiques qui me manquait, néophyte que je suis. Très vite, je me suis retrouvée « larguée », voguant sur des flots de calculs et formules, submergée par un tsunami de questions qui ne trouvaient pas de réponses. Mais ça veut dire quoi ? Ça signifie quoi ? Et cette lettre, c’est un A comme /a/ ? Quelle est l’utilité de ses formules ? A quoi ça sert ?

Florian qui encadre les TD de mathématiques à l’université de Marseille Saint Charles et Luminy depuis maintenant trois ans3, a réagi en bon pédagogue. Il a pris le temps de m’expliquer le contenu de ce beamer dans notre langage commun : le français de tous les jours ! Toutes ces formules obscures me paraissaient certes plus claires mais malgré tout, je restais dans le brouillard. Un de ces brouillards rasants que l’on retrouve souvent dans ces cimetières de vieux films d’épouvante en noir et blanc…

C’est quoi une fonction APN, un polynôme et une fonction puissance ?

Soit mN et f une fonction booléenne vectorielle de F2mF2m. On dit que f est presque parfaitement non-linéaire (ou Almost Perfectly Nonlinear en anglais, ou APN) si ∀a,bF2m,a≠0, l’équation f(x + a) + f(x) = a au plus 2 solutions dans F2m.

En clair et en simplifié, f est un règle pour transformer une suite de 0 et de 1 en une autre suite de 0 et de 1 qui a une certaine propriété.

Chaque fonction booléenne vectorielle de F2mF2admet une représentation unique en un polynôme d’une seule variable à coefficients dans F2m.

En clair et en simplifié, on peut écrire f sous la forme d’une somme de puissances de x.
Par exemple f(x) = x7 + x4 + x2 + x + 1

Les premières fonctions APN que l’ont a trouvé étaient des fonctions dites « puissance », c’est à dire qu’elles ne sont constitués que d’une seule puissance de x.
Par exemple : f(x) = x5

C’est quoi la différence entre une fonction APN et une fonction puissance ?

Ce n’est pas la bonne question. Parce qu’une fonction peut très bien être l’une ou l’autre, ou ni l’autre ni l’autre, ou les deux.

4

Fouiller la crypte

« Les premières cryptes (aussi appelées anciennement crutes, croutes ou grottes) ou grottes sacrées ont été taillées dans le roc ou maçonnées sous le sol, pour cacher aux yeux des profanes les tombeaux des martyrs ; plus tard, au-dessus de ces hypogées vénérées par les premiers chrétiens, on éleva des chapelles et de vastes églises ; puis on établit des cryptes sous les édifices destinés au culte pour y renfermer les corps des saints recueillis par la piété des fidèles. »
Wikipedia

 

Florian réalise alors un schéma qui m’éclaire un peu plus. Mais malgré cela, tous ces termes étant beaucoup trop abstraits à mon goûts, je déterminais alors la fonction APN comme étant un crâne ! Partons d’un tas d’ossements où l’on cherche les os « crâne ». Le tas d’ossements représente les fonctions puissance et les crânes sont non seulement des fonctions puissance puisqu’elles font partie du tas d’ossements mais en plus elles sont fonction APN. Dans tout le tas d’ossements, au final, il n’a été possible de trouver que deux crânes : un représente les fonctions Gold et l’autre les fonctions Kasami. Pour caricaturer, on a trouvé deux types de crânes, par exemple de femme et d’homme. C’est ainsi que nous nous sommes retrouvés à chercher un certain type de crâne, Gold et Kasami, dans un plus gros tas d’ossements, une crypte, où se trouve le premier tas d’ossements que nous avions considéré. Cette crypte était l’ensemble des polynômes. Et au milieu de ces ossements, se cachaient des crânes fonctions APN parce que des crânes fonctions APN, il n’y en a vraiment pas des masses par rapport à toutes les fonctions qui existent.

Il faut bien comprendre ici que les fonctions puissance sont des polynômes particuliers. Aussi, les ossements du premier tas sont des os particuliers de la crypte, ils constituent un sous-ensemble des os de la crypte entière. Tout le sujet de ma thèse est de savoir s’il existe ou non d’autres types de crânes dans cette crypte. Pour l’instant, tous ceux qui ont travaillé sur le sujet et moi-même n’avons pas pu fouiller toute la crypte même si nous l’avons déjà bien déblayée. Je m’occupe maintenant des recoins sombres5. Comme nous n’avons toujours trouvé que des crânes d’hommes et de femmes, nous avons émis la conjecture suivante : « dans notre crypte, il n’y a que des crânes d’hommes et de femmes ».

Mais, si on trouve un crâne de chien ? C’est possible, non ? Imagine qu’une petite mamie ait voulu être enterrée avec son petit chien.

Et bien, si l’on découvre un crâne de chien (fusse-t-il mâle ou femelle) cela voudra juste dire que la conjecture était fausse, et si c’est moi qui le trouve je deviens célèbre dans le monde des mathématiques.

Avant de formuler sa réponse de la sorte, Florian répondait : « On ne sait pas si on va trouver un crâne de chien ! » « Mais comment ça on ne sait pas ? » « Non, on ne sait pas. » « Mais enfin si tu trouves un crâne de chien tu es bien capable de me dire ce qu’il va advenir ensuite, non ? » « On ne sait pas. » Je suppose qu’en mathématiques on n’envisage rien à l’avance mais tout de même ! Et il a fallu que je m’obstine pour obtenir une réponse qui me convienne mieux mais qui après tout ne convient peut-être en rien au monde des mathématiques.

Message crypté

Que penser de cette histoire de fouille approfondie, de ces moments passés à discuter et à réfléchir, à creuser et à déblayer comme des apprentis archéologues ?

  • D’abord, que nous n’avons certainement pas choisi d’aller fouiller dans une crypte par hasard. Florian travaillant la cryptographie, c’est donc très naturellement que mon instinct a choisi comme image de comparaison des ossements et des crânes à aller dénicher dans le fin fond d’une crypte. Ce n’est que le lendemain, sous la douche6 que j’ai réalisé que ce choix inconscient était fait en toute conscience par mon moi intérieur.
  • Ensuite, qu’une crypte est le lieu caché par excellence en son sens même. Du latin crypta et du grec ancien κρύπτη, krýptê, de κρύπτω kríptô (« cacher »). Alors cacher quelque chose dans une crypte rend la chose encore plus difficilement trouvable car pour cela, il faudrait d’abord réussir à trouver le lieu où se terre la crypte en question (c’est-à-dire en avoir ses coordonnées géographiques) pour pouvoir ensuite dénicher l’objet caché. Et pour peu que l’on n’en est donné aucune description comment alors savoir que l’objet trouvé fut l’objet caché ?
  • Enfin, que toutes ces histoires de langage crypté sont séduisantes pour l’idée fabuleuse d’en révéler le secret. C’est comme une grande chasse au trésor ! C’est à celui qui trouvera l’objet caché en premier. C’est à celui qui saura trouver ce qui se cache dans la crypte : mensonge ou vérité qu’importe. Quels secrets s’y cachent et rient à notre barbe ? Mais le charme du sens caché ne réside-t-il pas dans le mystère de sa compréhension ? En trouver le sens n’est-il pas le risque d’en dissoudre l’enchantement et avec d’en voir s’échapper toute la magie ? Quant à le révéler au grand jour, à qui revient la responsabilité d’une telle décision ? On se souvient de ce qui s’échappa de la boîte (jarre) qu’ouvrit Pandore… Et l’on se rappelle du terrible secret qui se cachait derrière la porte que la Barbe Bleue ne voulait que l’on n’ouvre… Certains secrets ne devraient-ils pas rester cachés à tout jamais ?

Aujourd’hui, les fonctions APN restent encore un mystère à mes yeux parce que je n’en comprends toujours pas vraiment le sens mathématique, et pour Florian, le seul mystère qui subsiste encore à ses yeux est de savoir où sont les fonctions APN car elles ne sont vraiment pas nombreuses et absolument pas triviales. C’est à ce titre qu’on peut les imaginer dans un jeu de cache-cache régi par un désordre assimilable à ce tas d’ossements éparses où l’on ne saurait dire combien de crânes s’y trouvent, enfouis sous l’amalgame des os, masse confuse.

Dans le fond, je crois que j’aime beaucoup les mathématiques pour tout ce qu’elles réveillent en moi, cette curiosité de l’enfant qui cherche inlassablement jusqu’à trouver. Jamais il ne se fatigue. Il a « […] la rigueur du regard d’indien qui chez les antiquaires, les chercheurs et les fous de livres ne continue à brûler que trouble et maniaque. » (Walter Benjamin) J’ai retrouvé le goût de la quête, de ce mystère qui m’échappe alors que je le frôle du bout des doigts, que je suis si proche de la solution et qu’il s’enfuit encore, repoussant encore plus loin les limites de ma recherche. Est-ce que les mathématiciens seraient des archéologues masqués, sortes d’Indiana Jones secrets ?

  1. Yet Another Conference on Cryptography []
  2. Résumé que vous retrouvez sur le site des Journées Codage et Cryptographie 2012 qui se sont déroulées à Dinard du 7 au 12 Octobre et où le mathématicien a aussi eu l’occasion de présenter son travail. []
  3. L1 Physique-Chimie les deux premières années et Maths-Info cette année. []
  4. Ceci est le silence de ma grande confusion intérieure. []
  5. Tellement sombres que des fois ça fait peur ! []
  6. Haut lieu de réflexion comme expliqué dans un précédent article. []