Séminaire de Cryptographie

Accueil     Présentation     Archives

Valentin Suder


Permutations complètes en caractéristique 2

Dans ce travail, nous nous intéressons aux permutations complètes, c’est-à-dire aux fonctions bijectives $x\mapsto f(x)$ telles que $x\mapsto f(x)+x$ soient aussi bijectives. Plus particulièrement, nous nous intéressons aux permutations complètes sur les corps finis $\mathbb{F}_{2^n}$. En caractéristique 2, la définition des permutations complètes coincide avec celle des orthomorphismes. Nous pouvons donc utiliser cette correspondance pour mettre à jour plus de propriétés et de résultats de ces objets combinatoires. En effet, malgré la multitude de travaux se concentrant sur les permutations complètes (et orthomorphismes) apparus depuis l’introduction du concept par Mann dans les années 40, il semble que peu de propriétés générales ou de classes de telles fonctions soient connues. Parmi ces classes de fonctions, la plupart sont monômiales, binômiales voire trinômiales et/ou affines. Dans cet exposé, nous commencerons par introduire la notion de permutations complètes ainsi que les propriétés de bases, et montrerons quelques unes des applications les plus courantes. Nous verrons donc les problèmes héritée s de ces applications. Dans un second temps, nous démontrerons quelques nouvelles propriétés des permutations complètes. Nous ré-explorons aussi le lien entre polynômes de permutations cyclotomiques et permutations complètes et caractérisons complètement les ‘permutations complètes cyclotomiques’ dans le cas des corps finis en caractéristique 2. Nous conclurons en proposant, par le biais d’un certains nombre de conjectures et d’observations sur ces nouvelles classes, une extension ‘géométrique’ des permutations complètes aux partitions régulières sur les corps finis.