Cal4doc : Séminaire de Calcul Formel des Doctorants du Plateau

Le calcul du groupe de classes, du régulateur et des unités fondamentales d'un corps de nombres est une tâche fondamentale en théorie des nombres. Ce problème est aussi utilisé dans l'élaboration et l'attaques de cryptosystèmes asymétriques.

Dans cet exposé, nous nous intéresserons à une nouvelle variations de l'algorithme sous-exponentiel de Buchmann dans lequel les relations sont calculée à l'aide des techniques de lattice sieving tandis que les unités sont dérivées par des méthodes p-adiques. Les premiers résultats de ce projet de recherche en court montrent une nette amélioration pour les corps de petit degré ( n < 10 ).

L'étude du groupe de classes d'idéaux d'un corps de nombres est un problème de théorie des nombres permettant notamment la résolution d'équations Diophantiennes, la vérification de conjectures non prouvées, ainsi que la représentation de groupes de matrices sur un corps de nombres. Dans le cas des corps quadratiques, le difficulté de résoudre le problème du logarithme discret dans le groupe de classes a attiré l'attention de la communauté cryptographique au début des années 90. Plusieurs cryptosystèmes ont été proposés reposant sur ce problèmes, et les attaques disponibles à ce jour sont sous-exponentielles en L(1/2), c'est à dire plus lentes que pour la factorisation d'entier RSA de taille équivalente qui a pour complexité L(1/3). Les récents travaux sur les isogénies entres courbes elliptiques ont mis en évidence l'importance du rôle des calculs concernant le groupe de classes d'idéaux d'un corps de nombres quadratique dans l'évaluations d'isogénies ainsi que la description du groupe d'endomorphismes d'une courbe. Durant l'exposé, nous prendrons le temps de décrire le groupe de classes d'idéaux d'un corps de nombres ainsi que les algorithmes sous-exponentiels classiques permettant d'en calculer la structure. Ensuite, nous nous intéresserons à des résultats sur la sécurité des cryptosystèmes basés sur les corps de nombres avant de terminer par des travaux en cours sur des améliorations pratiques de l'algorithme d'évaluation d'isogénies de Bröker-Charles-Lauter.

Dans cet exposé, on présentera une variante de l'algorithme F4 pour le calcul de bases de Gröbner, permettant de résoudre plus rapidement des familles de systèmes polynomiaux ayant des expressions similaires. On donnera une illustration de l'efficacité de cette variante sur les problèmes de calculs d'indices sur courbes elliptiques, et plus particulièrement sur la courbe Oakley 'Well Known Group' 3 du standard IPSEC.

Le but de cet exposé est de présenter de façon assez élémentaire la notion de polygone de Newton d'un polynôme et d'expliquer comment, notamment, on peut en déduire un critère d'irréductibilité des polynômes à coefficients rationnels. Je commencerai par des rappels très généraux sur les valuations sur un anneau commutatif afin d'éclaircir la signification de ce terme. Puis je donnerai les preuves détaillées nécessaires donnant le critère d'irréductibilité pour des polynômes à coefficients rationnels.

The short history of modern computers has seen an exponential growth of cheaply available computing power, a trend already theorized by Gordon Moore in 1965. While the impending death of Moore's law may have been greatly exaggerated, it's ultimate demise is an inescapable fact. Needless to say, this prompted the development of alternative models to the tried-and-true silicon-based designs. The most promising substitute lies perhaps in quantum computing which can lead, by harnessing the counter-intuitive quantum peculiarities of matter, to polynomial or even exponential speed-up.

This short talk is intended as a general overview of quantum computation for non-physicists. We will begin by recalling some basic facts about quantum mechanics, with the minimal amount of formalism needed, and see that quantum computers owe their performance to two fundamental properties: quantum superposition and quantum entanglement. We will then be ready to understand the two main quantum algorithms: Grover's database search and Shor's polynomial integer factorization. The application of quantum entanglement to cryptographic protocols will then conclude the presentation.

Un code est dit LDPC (Low Density Parity Check) s'il existe une matrice creuse dont il est le noyau. De tels codes sont très fréquemment utilisés dans la pratique du fait des remarquables performances des algorithmes utilisés pour les décoder (Min-Somme, Somme-Produit, Bit Flipping etc…).

Le plus souvent ces codes sont générés de façon aléatoire. Toutefois, il existe également un certain nombre de constructions basées sur l'utilisation d'objets combinatoires tels que les designs ou les structures d'incidences.

Dans cet expose, après une introduction sur les codes LDPC, je présenterai de nouvelles structures d'incidences basées sur les relations d'incidence entre des drapeaux du plan affine et certaines coniques planes. Ces structures fournissent des codes LDPC vérifiant d'intéressantes proprietés pour les performances des algorithmes de décodage itératif.

L'anneau des entiers p-adiques Z_p est à l'anneau des entiers Z, ce que celui des séries formelles C[[x]] est à celui des polynômes C[x].

On commencera par définir plus explicitement ce que sont les entiers p-adiques et de manière générale les nombres p-adiques pour un anneau quelconque. On étudiera l'arithmétique détendue inventée par J. van der Hoeven dans les cadres des séries formelles et on généralisera les algorithmes d'addition naïve et de multiplication détendue pour les p-adiques.

Une des applications majeures de ces algorithmes est la capacité à calculer rapidement des éléments dont les coefficients sont récursifs. L'on verra donc comme application la division et si l'on a le temps le calcul de racines r-èmes et p-èmes dans Z_p. Une démonstration en Mathemagix est prévue.

It is almost cliché to recall that integer factorization is a challenging algorithmic problem, be it from a purely theoretical or from a more pragmatic standpoint. On the utilitarian side, the main interest in integer factorization certainly stems from cryptography given the ubiquity of the RSA cryptosystem, based on the premise that factoring large integers is computationally impracticable. More prosaically, integer factorization is also one of the main ingredients in a lot of number theoretical algorithms.

In this short introductory presentation, I will sketch the integer factorization landscape, from the Dark Ages of the exponential methods to the modern times of the sieving algorithms, dipping a toe (if time permits) in the troubled and perplexing quantum waters.

Please note that this survey will merely scratches the surface, as giving detailed theoretical backgrounds on all the factorization techniques is out of question in such a short time frame.

While the slides will be in English, the talk is likely to be in French unless there is an overwhelming, masochistic demand to endure and decipher the speaker's muddy accent.

Biography

A wannabe physicist in a previous life, Jerome Milan ended up working, by a improbable twist of events, as a software programmer in one of France's supposedly premier scientific university. Master of disguise, he is now impersonating an overaged PhD student.

While he is not busy daydreaming, mourning over his lack of value, or distorting reality to appear as knowledgeable, he enjoys writing about himself at the third person, for it gives him the illusionary feeling to be much more important than he really is.

Nous allons montrer comment passer par la caractéristique positive pour ne pas avoir à se soucier de la taille des coefficients intervenant dans les calculs d'invariants primaires et secondaires. Une partie de l'exposé traitera donc d'invariants. Mais nous parlerons aussi de factorisation sur un corps de nombres.

L'exposé commencera par une brève introduction aux codes correcteurs d'erreurs sur les corps finis. On aborda ensuite le décodage en liste qui permet d'augmenter sensiblement le nombre d'erreurs corrigibles au détriment de l'unicité du mot décodé. Cette approche générale se conclura par l'étude de la borne de Johnson, borne qui permet de majorer le nombre d'erreurs que l'on peut décoder avec un algorithme de type décodage en liste. Ainsi, on verra une particularité intéressante de la borne de Johnson pour les codes définis sur F₂.

Dans un second temps, notre attention se portera sur des aspects plus algorithmiques, on regardera d'abord l'algorithme de décodage de Berlekamp-Welsh, algorithme de décodage unique, qui donna l'essence au premier algorithme de décodage en liste, l'algorithme de Sudan. On présentera ce dernier, ainsi que son extension qui est due a Sudan et a son étudiant Guruswami.

Je me propose de raconter comment on peut s'y prendre pour évaluer numériquement la fonction arctangente à grande précision en bonne complexité. Par exemple, comment calculer rapidement arctan(1/3+2i/5) ou encore arctan(e) à 10^-10000 près ? La méthode que j'exposerai est due à D.V. et G.V. Chudnovsky, ses ingrédients centraux sont le «scindage binaire» et l'algorithme «bit burst». Elle est complétée par des algorithmes, développés dans ce contexte par J. van der Hoeven, qui permettent dans de contrôler automatiquement la précision des calculs pour garantir le résultat.

Au-delà de l'exemple d'arctangente, tous ces algorithmes s'étendent à la classe des fonctions solutions d'équations différentielles linéaires à coefficients polynomiaux, qui recouvre un grand nombre de fonctions élémentaires et de fonctions spéciales.

(On trouvera un autre éclairage du sujet dans cet exposé de P. Zimmermann. Malgré l'exemple filé commun — c'est un choix naturel — j'espère que sa présentation et la mienne seront plus complémentaires que redondantes.)

Lorsqu'une courbe est définie par une équation polynômiale en deux variables x et y, il se peut que des lieux singuliers apparaissent, un point double ou un point de rebroussement par exemple. La désingularisée de cette courbe est une courbe vivant dans un espace de dimension plus grande et telle qu'il existe un morphisme birationnelle de cette courbe vers la courbe de départ. De façon informelle, on pourrait dire que la projection de la désingularisée sur le plan (x, y) est la courbe de départ.

Savoir exprimer y en fonction de x, c'est-à-dire voir y comme une racine du polynôme, permet de comprendre comment l'on obtient cette désinguralisée. Si l'on se place dans C, y est alors une série de Puiseux. Le corps des séries de Puiseux en x, que j'expliquerai, forme la clôture algébrique du corps C((x)) des séries de Laurent. Dans une première partie, je donnerai l'algorithme naïf dit de Newton-Puiseux qui permet de calculer chaque terme de la série de Puiseux y à partir d'un polynôme annulateur.

Dans une seconde partie, je parlerai de fermeture algébrique qui est le sujet-même de ma thèse. Un élément d'une extension algébrique de K(x) est dit entier sur K[x] s'il est racine d'un polynôme unitaire à coefficients dans K[x]. L'intérêt de ces élément est que le calcul de la fermeture algébrique de K[x] dans K(x)[y]/(P (x, y)) est intimement lié à la désinguralisation de la courbe algébrique définie par P.

Il est bien connu que les développements en série de Taylor de fonctions solutions d'équations différentielle linéaire à coefficients polynomiaux (ou D-finies) ont des coefficients qui vérifient une récurrence linéaire. La même propriété est vérifiée par les coefficients des développements de ces fonctions en série de Tchebychev (c'est-à-dire sur la base des polynômes de Tchebychev). Ces développements possèdent des propriétés intéressantes du point de vue de l'approximation, ce qui motive leur étude et la recherche d'algorithmes efficaces pour leur calcul. Alors que de tels algorithmes sont classiques dans le cas des séries de Taylor, les méthodes connues pour les séries de Tchebychev n'avaient pas été étudiées du point de vue de la complexité.

Dans cet exposé, je décrirai les algorithmes existants et je donnerai un nouvel algorithme plus efficace réalisé lors de mon stage. J'exposerai aussi la théorie mathématique sur laquelle reposent ces algorithmes.

In the following we are going to see the benefits of a strategy involving large prime variations for the computation of the structure of the ideal class group of an imaginary quadratic number field. Hafner and McCurley described an algorithm which computes the group structure of the ideal class group in subexponential time. It is divided into two major steps: first we compute a "relation matrix" from relations satisfying a smoothness condition for a bound B. Then we compute the HNF and SNF of this matrix thus obtaining the group structure. The linear algebra step is the most expensive one. Naturally we want to decrease the size of B in order to treat smaller matrices, but this slows down the relation collection phase, that is why we want to improve the relation collection step. This can be achieved by using the large prime variant, at the cost of producing a denser matrix after the recombination phase.

We have studied the single and double large prime variants in order to speed up the relation collection phase. This technique has been used in factorization and studied by Jacobson in our context. His conclusion was that the relation matrix gets more dense, and thus slows down the computation of the HNF. Indeed, the algorithm used at the time assumes the matrix is sparse. But Vollmer described how we can get rid of the dependence on the density. This allowed us to revisit large prime variants. Vollmer's technique for computing the HNF relies itself on our capacity to solve diophantine linear systems. It was not implemented at the time Volmer published its algorithm, but since then efficient diophantine solvers are available, in particular in IML, the library provided by Arne Storjohann. In order to prepare the matrix we have also studied how to filter the matrix before giving it to the solver, using in particular gaussian elimination techniques. These techniques are well known in the context of factorization but need some slight modifications for our purposes.

Soit K un corps de caractéristique p, une extension d'Artin-Schreier est une extension de corps engendrée par un polynôme de la forme X^p - X - a. Toute extension séparable de degrée p peut être exprimée comme une extension d'Artin-Schreier, en particulier toute extension de degré p sur un corps fini.

Les tours d'Artin-Schreier apparaissent naturellement en théorie des nombres, par exemple dans le calcul des points de p-torsion d'une variété abélienne. On présente ici des algorithmes asymptotiquement rapides pour les opérations arithmetiques de base dans les tours d'Artin-Schreier et pour certaines operations avancées tel le calcul du morphisme de frobenius ou des traces.

Cette étude, en collaboration avec È.Schost de l'University of Western Ontario, a fait l'objet d'exposés à C4 et au CMS Winter Meeting et fait l'objet d'un papier soumis à ISSAC.