Je suis depuis le début de ma thèse dans le projet Analytic combinatorics and probabilistic number theory financé par le FWF (fonds national de recherche en Autriche). Il s'agit d'un réseau de dix sous-groupes de recherche basés dans les universités de Vienne, Graz, Linz, Leoben et Salzburg. Ce rèseau emploie des doctorants et post-doctorants, organise des colloques et des séminaires, favorise les collaborations inter-groupes mais aussi internationales par le financement de visites. Le site web rend compte des publications issues de ces collaborations. Les thèmes de recherche sont la combinatoire (étude probabiliste, méthodes analytiques), la théorie des nombres (systèmes dynamiques, numération), ainsi que leurs applications (en cryptographie par exemple).

Après la fin de ma thèse j'ai travaillé à Caen dans le projet LAREDA, financé par l'ANR. Ce project est partagé entre l'université de Caen et l'université de Montpellier. Dans ce projet on étudie l'algorithme LLL qui a plusieurs applications en cryptographie, théorie des nombres, géométrie algébrique. L'algorithme a été développé par Lenstra, Lenstra et Lovasz en 1982, mais il est difficile à mettre en oeuvre sous sa forme originale. L'objectif du projet est l'analyse du LLL pour mieux comprendre les temps d'exécution, les sorties et la structure dynamique.

Système de numération

Je m'intéresse aux propriétés analytiques et probabilistes des chiffres dans un système de numération. En particulier un système de numération décrit des éléments par une séquence de chiffres. Il y a plusieurs méthodes pour définir un tel système, par exemple dans un groupe muni d'un épimorphisme, dans une classe de graphes avec une propriété donnée ou dans un anneau de polynômes formels. Je me concentre sur la dernière méthode et en particulier sur les anneaux de polynômes à coefficients dans les entiers ou dans un corps fini. Étant donné un polynôme $P(x)=x^d+b_{d-1}x^{d-1}+\ldots+b_0\;\in\mathbb{Z}[x]$ et l'ensemble de chiffres $\mathcal{N}=\{0,\ldots,|b_0|-1\}$, on dit que $(P,\mathcal{N})$ est un système de numération canonique (CNS) si tout élément $\gamma$ de $\mathbb{Z}[x]/(P(x)\mathbb{Z}[x])$ admet une unique représentation $\gamma=a_0+a_1 x+\ldots+a_{l(\gamma)}x^{l(\gamma)}$ avec $a_i\in\mathcal{N}$ et $l(\gamma)\in\mathbb{N}$. Si $P$ est irréductible et $\alpha\in\mathbb{C}$ est une racine de $P$, ceci revient à dire que tout élément de $\mathbb{Z}[\alpha]$ a une unique représentation en base $\alpha$ de la forme $a_o+a_1\alpha+\ldots+a_{l(\gamma)}\alpha^{l(\gamma)}$.

La base $\alpha$ et l'ensemble de chiffres ne sont pas uniques pour $\mathbb{Z}[\alpha]$, mais avec le couple $(P,\mathcal{N})$ ou $(\alpha,\mathcal{N})$ fixé on peux considérer la distribution des chiffres.À chaque système de numération est associé un pavé de $\mathbb{R}^n$ où $n$ est le degré de $P$. Mes recherches portent sur deux classes. La première est constituée d'analyse des fonctions additives. Ces fonctions sont définies dans un système de numération et opèrent sur les chiffres seulement. La somme des chiffres en est un exemple bien connu. Sa répartition dans les classes de congruence est analysée par Gelfond et la somme analytique de sommes de chiffres est analysé par Delange. Bassily et Katái montrent que la distribution asymptotique pour une fonction additive dans un système de numération dans $\mathbb{N}$ suit une loi normale. Je m'intéresse à la généralisation de ces résultats dans d'autres systèmes de numération. Par exemple, les systèmes de numération dans $\mathbb{N}$ sont reliés aux systèmes dans $\mathbb{F}[X]$ avec $\mathbb{F}$ un corps fini et les systèmes dans $\mathbb{Z}[\alpha]$ à ceux dans $\mathbb{F}[X,Y]/P(X,Y)\mathbb{F}[X,Y]$ avec $P$ un polynôme à coefficients dans $\mathbb{F}[X]$.

En outre la distribution de sommes des chiffres sur les valeurs polynomiales ou les nombres premiers est intéressante. La première est motivée par le résultat de Bassily et Katái, qui donne la distribution asymptotique pour les fonctions additives sur les valeurs polynomiales. La seconde est motivée par un nouveau résultat de Mauduit et Rivat concernant la somme $\sum_{p\leq P}\exp(2\pi i\alpha s_q(p))$ oú $p$ parcourt les nombres premiers, $\alpha$ est réel et $s_q$ est la somme des chiffres en base $q$. Il est aussi intéressant d'analyser cette somme sur les nombres entier sans grand facteur premier.

Nombres normaux

La deuxième classe est associée aux nombres normaux. Il y a deux raisons. La première est que chaque système de numération et son pavé de $\mathbb{R}^n$ permettent de définir une notion de nombre normal dans ce système. La deuxième est qu'on a recours à la même technique de démonstration que pour la distribution de chiffres évoquée précédemment. En particulier il s'agit d'évaluer des sommes d'exponentielles.

Je m'intéresse à la construction de nombres normaux dans ces systèmes. Par exemple pour le système décimal la construction de Champernowne
\[0.1\,2\,3\,4\,5\,6\,7\,8\,9\,10\,11\,12\,13\,14\,15\,16\,17\,18\,19\,20\]
est un nombre normal dans ce système. Jörg Thuswaldner, Robert Tichy et moi montrons que cette construction est possible pour une plus grande classe de fonctions, plus précisément on peut prendre une fonction entière pour la construction.

La définition des nombres normaux est transférée à d'autres systèmes de numération comme dans des corps algébriques ou des corps finis. Par exemple dans les entiers de Gauss il est possible de prendre une polynôme à coefficients dans $\mathbb{C}$ pour construire un nombre normal dans le système de numération.

Je veux analyser ces constructions non seulement dans les systèmes de numération ci-dessus, mais aussi dans les systèmes dans un groupe infini. En particulier c'est très intéressant de considérer la structure fondamentale d'un nombre normal et sa relation à la loi uniforme. Je considère également d'autres constructions de nombres normaux comme présentée par Dumont et Thomas ou Edgardo Ugalde.

LLL-algorithme

Dans le groupe LAREDA a Caen, l'objectif a été l'analyse de l'algorithme LLL. En particulier Brigitte Vallée et moi modélisons cet algorithme par des tas des sables avec lesquels on montre des estimations pour le temps d'exécution. Ces estimations sont très importantes en cryptographie. Plus précisément on peut calculer la clé secrète $d$ dans un système de cryptographie RSA, si elle est trop petite (par rapport au module $n$). Avec le méthode de Wiener c'est possible si $d\leq n^{0.25}$. Dans un récent article de Boneh et Durfee, un réseau et l'algorithme LLL sont utilisés pour montrer que c'est même possible si $d\leq n^{0.292}$. L'idée est de trouver un zéro d'un polynome. Ce problème a un lien avec un réseau dont la structure est très intéressante. Plus précisément, ce réseau se compose de blocs qu'on peux réduire avec LLL séparément. Cela aboutit à une accélération du temps d'exécution, car la dimension de chaque bloc est plus petite que la dimension du réseau. Le phénomène n'est pas limité à ce réseau : on peut appliquer la décomposition en blocs àd'autres polynomes. L'objectif est donc de caractériser ces polynômes et de développer un programme pour réduire le réseau de manière effective.