Institut de Mathématiques de Luminy

SÉMINAIRES 2012
Arithmétique et Théorie de l'Information

Responsable: C. Ritzenthaler
Horaires: Le jeudi à 11h
Salle: Amphi Herbrand du 1er étage, salle 130-134, I.M.L., Groupe des Laboratoires de Luminy (CNRS).

Planning

Régis Blache

jeudi 13 décembre
Régis Blache
(Univ. Antilles-Guyane, Guadeloupe)
Congruences pour les fonctions L

Webpage: http://www.univ-ag.fr/fr/annuaire/regis_blache.html

Résumé : On va présenter une congruence pour les fonctions L provenant de sommes de caractères additifs associées à des polynomes sur un espace affine. Elles proviennent d'un examen attentif d'opérateurs p-adiques introduits par Dwork.
Ces congruences sont très semblables à celles données par Manin pour le numérateur de la fonction zêta d'une courbe définie sur un corps fini. Pour les rendre explicites dans certains cas particuliers, on sera amenés à étudier un opérateur semi-linéaire, analogue de celui de Cartier Manin dans notre situation.


Guénaël Renault

jeudi 29 novembre
Guénaël Renault
(LIP6, Jussieu)
Sur la résolution des systèmes polynomiaux intervenant lors du calcul d'indice dans les courbes elliptiques

Webpage: http://www-polsys.lip6.fr/~renault/

Résumé : Dans cet exposé, je présenterai des résultats récents sur le calcul d'indice pour la résolution du problème du logarithme discret dans le groupe des points d'une courbe elliptique définie sur un corps fini (ECDLP). Ils se basent sur l'algorithme introduit par Semaev en 2004 et développé ensuite par Gaudry et Diem. Le résultat principal est la mise en évidence de structures spécifiques des systèmes polynomiaux intervenant dans ce calcul. Plus précisément, les systèmes polynomiaux sont ceux intervenant dans la résolution du problème sous-jacent de décomposition de points. Suivant les courbes (modèle, caractéristique) étudiées, différentes structures ont pu être mises en évidence : présence de symétries ou formes multi-homogènes. L'utilisation de ces structures ont permis de gagner tant en pratique qu'en théorie sur la résolution du problème de décomposition.
Résultats basés sur des collaborations avec J.-C. Faugère, P. Gaudry, L. Huot, L. Perret et C. Petit.


logo Technical University of Denmark

jeudi 22 novembre
Johan Nielsen
(Technical University of Denmark)
The Wu list-decoder for Reed-Solomon codes
using the Euclidean algorithm

Webpage: http://www.mat.dtu.dk

Abstract: In 2007 Wu published a new list decoder for Reed-Solomon codes. It has similarities with the famous Guruswami-Sudan algorithm, most notably the decoding radius, but works in a significantly different manner. Importantly, for high-rate codes the Wu list-decoder has lower complexity than the Guruswami-Sudan.
At the core, it is an extension of the minimum-distance decoder using the Berlekamp-Massey algorithm (BMA). The derivation, however, is somewhat involved and requires extensive arguments on the precise workings on the BMA.
I will describe how the Wu list-decoder works, but using the Extended Euclidean algorithm as its main engine. This reveals more clearly the algebra underlying the decoder.


Stéphane Louboutin

jeudi 15 novembre
Stéphane Louboutin
(IML, Marseille)
Corps CM non galoisiens principaux

Webpage: http://iml.univ-mrs.fr/~loubouti/

Résumé : Une généralisation du problème du nombre de classes 1 pour les corps quadratiques imaginaires conjecture qu'il n'y a qu'un nombre fini de corps CM de nombres de classes donné.
Le problème est résolu pour le cas abélien, à peu près résolu pour le cas galoisien, seulement conjectural pour le cas non galoisien. Nous l'abordons ici pour une famille de corps CM non galoisiens de degrés non fixes par avance.


Xavier Roulleau

jeudi 25 octobre
Xavier Roulleau
(Univ. Poitiers)
Arithmétique des surfaces de Fano

Webpage: http://www-math.sp2mi.univ-poitiers.fr/~roulleau/

Résumé : Une surface de Fano paramètre les droites contenues dans une hypersurface cubique lisse de dimension 3. C'est une surface lisse de type général dont nous montrons qu'elle satisfait à la conjecture de Tate. Nous discutons ensuite d'un algorithme qui permet de déterminer sa fonction zeta (dans le cas où le corps de base est un corps fini) et d'obtenir des invariants intéressants de cette surface.


logo universite blaise pascal clermont-ferrand

jeudi 18 octobre
Joël Cohen
(Univ. Blaise Pascal, Clermont-Ferrand)
Un théorème de Paley-Wiener
sur les groupes p-adiques tordus

Webpage: http://math.univ-bpclermont.fr/~cohen/

Résumé : Si G est un groupe réductif (pas nécessairement connexe, ie tordu) p-adique et f une fonction complexe lisse à support compact sur G, la transformée de Fourier de f est à variable dans les représentations complexes lisses de G. Le théorème de Paley-Wiener sur G caractérise l'image de cette transformée de Fourier et fournit une formule d'inversion.
Dans cet exposé, je donnerai d'abord quelques éléments de contexte et de motivation de ce problème autour du programme de Langlands. Puis j'expliquerai brièvement le résultat en lui-même.


Marusia Rebolledo

jeudi 14 juin
Amphi Herbrand, à 11h
Marusia Rebolledo
(Université Clermont-Ferrand 2)
Points rationnels de $X_0^+(p^r)$

Webpage: http://math.univ-bpclermont.fr/~rebolledo/

Résumé : En mêlant théorie analytique des nombres, géométrie arithmétique et algorithmique, Yuri Bilu, Pierre Parent, et moi-même avons montré que pour tout entier $r>1$ et tout nombre premier $p\geq 11, p\neq 13$, la courbe modulaire $X_0^+(p^r)$, quotient de la courbe $X_0(p^r)$ par l'opérateur d'Atkin-Lehner $w_{p^r}$ n'admet pas de point rationnel autre que ceux attendus (qui sont des pointes ou des points CM). Pour $r=2$ cela répond en partie à une question posée par Serre dans les années 70. Dans cet exposé, après avoir expliqué les résultats et ingrédients principaux, je m'attacherai plus en détail à la partie algorithmique de notre travail.


David R. Grant

jeudi 14 juin
Amphi Herbrand, après-midi
David R. Grant
(University of Colorado, USA)
Space-time codes coming from elliptic curves

Webpage: http://www.colorado.edu/math/people/professors/grant.html

Abstract: Space-time codes are sets of matrices used to make digital transmission for multiple-transit antenna systems more reliable. The most famous constructions come from representations of associative division algebras over number fields, but one can equally well use representations of the less familiar non-associative division algebras. I will discuss how the theory of elliptic curves can be used to build or classify 3- and 4-dimensional non-associative division algebras over number fields.


Pietro Corvaja

jeudi 7 juin
Pietro Corvaja
(Universit`a degli Studi di Udine, Italia)
Singularités de courbes algébriques sur un tore et nombre de points rationnels sur un corps fini.

Webpage: http://www.dimi.uniud.it/Members/pietro.corvaja

Résumé : Considérons une courbe algébrique $X$ sur un tore linéaire $G_m^2$. En caractéristique zéro, on peut majorer d'une manière presque optimale la plus grande multiplicité d'une singularité de $X$ en terme du degré et de la caractéristique d'Euler $\chi$ de $X$, en obtenant une majoration $$ \ll (\chi \deg X)^{2/3}$. Le résultat analogue en caractéristique finie ne vaut pas, mais une formulation plus faible sera présentée, et l'on montrera, dans le cas des corps finis, qu'elle entraine une estimation pour le nombre de points rationnels. On en déduit une nouvelle démonstration du théorème de Weil (hypothèse de Riemann pour les corps de fonctions).
Il s'agit de travaux en collaboration avec U. Zannier.


Christian Maire

jeudi 31 mai
Christian Maire
(LMB, Besançon)
Les pro-p-groupes "mild" en arithmétique

Webpage: http://lmb.univ-fcomte.fr/rubrique.php3?id_rubrique=123

Résumé : Au milieu des années 2000, John Labute a donné les premiers exemples de pro-p-extensions à ramification modérée de dimension cohomologique 2. Ce résultat s'obtient par l'étude de l'algèbre de Lie des pro-p-groupes en jeu. Plus récemment, Alexander Schmidt a étendu les techniques de John Labute et a montré que quitte à grossir convenablement l'ensemble de ramification modéré, les extensions deviennent "mild". Avec Blondeau et Lebacque, nous venons d'appliquer la méthode de Schmidt dans le cadre de la théorie d'Iwasawa.
Dans cet exposé nous reviendrons donc sur tous ces résultats et aborderons les derniers travaux de Blondeau et Labute sur les représentations p-adiques de tels pro-p-groupes.


jeudi 24 mai
Amphi Herbrand, à 1
1h
Emmanuel Hallouin
(IMT, Univ. Toulouse 2)
Obstructions globales à la descente pour les variétés

Webpage: http://www.math.univ-toulouse.fr/~hallouin/

Résumé : Dans ce travail, en collaboration avec Jean-Marc Couveignes, nous nous intéressons aux corps des modules et de définition de certaines variétés. Plus précisément, on souhaite trouver des exemples de variétés qui ne sont pas définies sur leur corps des modules. Partant du fait que de telles obstructions à la descente existent dans la catégorie des revêtements de courbes, nous produisons d'autres exemples dans certaines catégories de surfaces puis dans la catégorie des courbes lisses. On présentera plusieurs constructions permettant de passer d'une catégorie à une autre.


Sudhir Ghorpade

jeudi 24 mai
Amphi Herbrand, à 14h30
Sudhir Ghorpade
(IIT Bombay, India)
Affine Grassmann Codes and their Automorphisms

Webpage: http://www.math.iitb.ac.in/~srg/

Abstract: Reed-Muller codes are among the most widely studied and perhaps one of the best understood classes of linear error correcting codes. A distinct variant of Reed-Muller codes, called affine Grassmann codes, was recently introduced and studied. In this talk we will give an introduction to affine Grassmann codes, and discuss several of its properties. A particular emphasis will be on the determination of the automorphism group of affine Grassmann codes, a topic that has evolved considerably in the last couple of years, and a complete determination is now possible, thanks partly to a classical result of Chow (1949).
This talk is based on a joint work with Peter Beelen and Tom Hoeholdt (2010, 2012) and also with Krishna Kaipa (2012).


Ruud Pellikaan

jeudi 19 avril
Amphi Herbrand, à 11h
Ruud Pellikaan
(Eindhoven University of Technology, the Netherlands)
On coded-based public key crypto systems
that use algebraic geometry codes

Webpage: http://www.win.tue.nl/~ruudp/

Abstract: In the lecture coded-based public key crypto systems on several classes of codes are discussed. Let X be an algebraic curve over the finite field GF(q), let P be an n-tuple of GF(q)-rational points on X and let E be a divisor on X. Then C_L(X,P,E) is the algebraic geometry code that is obtained by evaluating the rational functions of the Riemann-Roch space L(E) at the points of P. The question is addressed of retrieving the triple (X,P,E) from the algebraic geometry code C_L(X,P,E). Let m=deg(E) and let g be the genus of X. Then the linear series of E gives an embedding Y of X in the projective space of dimension m-g in case m>2g. If moreover m>2g+1, then I(Y), the vanishing ideal of Y is equal to the ideal generated by I_2(Y ), the homogeneous elements of degree two in I(Y ). If n>2m, then I_2(Y)=I_2(Q), where Q is the image of P under the map from X to Y. These results imply that certain algebraic geometry codes are not secure if they are used in the McEliece public-key cryptosystem.


Marc Perret

jeudi 19 avril
Salle des séminaires, à 14h30
Marc Perret
(Laboratoire Émile Picard, Toulouse)
Quelques remarques sur les tours récursives
à la Garcia-Stichtenoth

Webpage: http://w3.grimm.univ-tlse2.fr/algo/perret/

Résumé : Il s'agit d'un travail en progrès, effectué en collaboration avec Emmanuel Hallouin. Nous allons prouver quelques propriétés générales sur les tours récursives. L'objet central est un certain graphe (assez proche d'un graphe déjà défini par Beleen) orienté et infini, construit à partir des données de base de la tour récursive.
Nous en déduisons par exemple que, sous une hypothèse très souvent vérifiée sur les exemples, au plus un seul beta_i (tel que défini par Tsfasman et Vladut) peut être non-nul dans la tour. La preuve utilise de façon cruciale de la théorie de l'intersection, la structure des valeurs propres de la matrice d'adjacence du graphe et un lemme diophantien bien connu dû à Kronecker.


Tammam Alasha

jeudi 12 avril
Tammam Alasha
(IML, Marseille)
Deterministic hashing
into different forms of elliptic curves

http://iml.univ-mrs.fr/ati/listeati.html


Robin Guilbot

jeudi 29 mars
Robin Guilbot
(IMT, Toulouse)
Un critère d'existence de points rationnels pour un diviseur d'une variété torique sur les corps C1

Webpage: http://www.math.univ-toulouse.fr/1-17731-Fiche-professionnelle.php?idFiche=548

Résumé : Les variétés toriques peuvent être considérées comme les variétés algébriques abstraites les plus simples car les plus ressemblantes à l'espace projectif P^n. En particulier elles sont naturellement munies d'un anneau de coordonnées homogènes (comme l'a montré David Cox en 1995), et graduées par un groupe abélien de type fini.
Les corps C1 (définis par Serge Lang en 1952) sont les corps sur lesquels toute hypersurface de P^n possède un point rationnel dès que son degré est inférieur ou égal à n. Il est naturel de se demander comment cette notion de petit degré peut s'étendre de l'espace projectif P^n a toute variété torique compacte.
Je traiterai le cas d'une variété torique n'ayant que des singularités sympathiques (variétés Q-factorielles) et expliquerai comment ces questions arithmétiques m'ont amené a construire des outils au contenu géométrique non trivial (notamment à un contrexemple à une conjecture de Cox sur les variétés toriques non projectives).


Johan P. Hansen

jeudi 22 mars
Salle des séminaires, à 14h30
Johan P. Hansen
(Aarhus University, Denmark)
Quantum Stabilizer codes from toric varieties

Webpage: http://home.imf.au.dk/matjph/

abstract Johan P. Hansen 2012


Luca de Feo

jeudi 22 mars
Amphi, à 11h
Luca de Feo
(PRISM, Versailles)
Encore un cryptosytème à base d'isogénies

Webpage: http://www.prism.uvsq.fr/~dfl/

Résumé : Il est bien connu que les graphes de courbes elliptiques isogènes ont une structure de graphe de Ramanujan, ce qui garantit des bonnes propriétés de mixage pour les marches aléatoires. Cette observation a été utilisée à plusieurs reprises pour construire des cryptosystèmes
basés sur la difficulté supposée de calculer explicitement une isogénie entre deux courbes elliptiques données. Rostovstev et Sotlbunov on proposé un protocole à la Diffie Hellman où les clefs secrètes sont des chemins d'isogénies de petit degré et la clef partagée est formée en composant la deux chemins secrets. La raison pour laquelle ce protocole marche est que le groupe des classes agit fidèlement et transitivement sur le graphe des courbes elliptiques isogènes. Le protocole de Rostovstev et Stolbunov est peu efficace et présente un intérêt purement théorique; les auteurs ont suggéré qu'il pourrait être utilisée dans un contexte post-quantique, cependant Childs, Jao et Soukharev ont montré qu'il existe un algorithme quantique qui calcule une isogénie entre courbes elliptiques ordinaires en temps sous-exponentiel.
L'attaque de Childs et al. repose justement sur l'action du groupe de classes, qui est commutatif. Dans ce travail, en commun avec Jao et Plût, nous proposons un cryptosystème basé sur la difficulté de calculer une isogénie entre courbes elliptiques supersingulières. Dans le cas supersingulier, l'anneau d'endomorphismes n'est pas commutatif et le groupe des classes n'est plus bien défini, par conséquent l'attaque de Childs et al. ne s'applique plus. En l'absence de l'action du groupe des classes, notre protocole d'échange de clef doit passer de l'information en plus par rapport à celui de Rostovstev et Stolbunov, il n'est cependant pas clair que cette information puisse aider à attaquer le protocole.
Notre protocole, déjà dans une implantation naïve en Magma, est sensiblement plus performant que celui de Rostovstev et Stolbunov. Nous avons étudié en détail le problème de son optimisation: avec un mélange de techinques classiques et nouvelles, nous présentons maintenant une implantation mixte en Sage/Cython/C qui a des performances comparables à celles de nombreux protocoles à base de couplages. En particulier, nous présentons un algorithme efficace pour le calcul d'isogénies de degré composé, ayant une structure combinatoire intéressante et parfois même étonnante.


Élodie Leducq

jeudi 15 mars
Élodie Leducq
(IMJ, Paris)
Fonctions puissances parfaitement non linéaires
sur une infinité d'extensions de Fp

Webpage: http://www.math.jussieu.fr/~elodieleducq/

Résumé :résumé Elodie Leducq


Christophe Petit

jeudi 8 mars
Christophe Petit
(Université catholique de Louvain)
On polynomial systems arising from a Weil descent

Webpage: http://perso.uclouvain.be/christophe.petit/index.html

Résumé : Polynomial systems of equations appearing in cryptography tend to have special structures that simplify their resolution. In this talk, we discuss a class of polynomial systems arising after deploying a multivariate polynomial equation over an extension field into a system of polynomial equations over the ground prime field (a technique commonly called Weil descent).
We provide theoretical and experimental evidence that the degrees of regularity of these systems are very low, in fact only slightly larger than the maximal degrees of the equations.
We then discuss cryptographic applications of (particular instances of) these systems to the hidden field equation (HFE) cryptosystem, to the factorization problem in SL(2,2^n) and to the elliptic curve discrete logarithm over binary fields. In particular, we show (under a classical heuristic assumption in algebraic cryptanalysis) that an elliptic curve index calculus algorithm due to Claus Diem has subexponential time complexity O(2^{c\,n^{2/3}\log n})\) over the binary field GF(2^n), where c is a constant smaller than 7/3.


Laurent Poinsot

jeudi 23 février
Laurent Poinsot
(LIPN, Paris 13)
Fonctions non booléennes presque parfaitement
non linéaires sur des groupes non abéliens

Webpage: http://lipn.fr/~poinsot/

Résumé : L'objectif de cet exposé est de présenter des définitions et caractérisations des notions classiques de fonctions booléenes APN et maximalement non linéaires adaptées au cas d'applications d'un groupe fini K dans un autre N avec la possibilité que l'un ou l'autre voire les deux groupes soient non abéliens.


Jeroen Sijsling

jeudi 16 février
Jeroen Sijsling
(IRMAR, Rennes)
Modèles canoniques de courbes de Shimura
de signature (1;e)

Webpage: http://sites.google.com/site/sijsling/


Valéry Mahé

jeudi 9 février
Valéry Mahé
(LMB, Besançon)
Suites à divisibilité algébriques

Webpage: http://lmb.univ-fcomte.fr/rubrique.php3?id_rubrique=159


jeudi 2 février
Mireille Car
(LATP, Marseille)
De nouveaux paramètres pour le problème de Waring sur F_{q}[T].


Mila Tukumuli

jeudi 26 janvier
Mila Tukumuli
(IML, Marseille)
Algorithmes d'interpolation de type Chudnovsky-Chudnovsky pour les courbes elliptiques

Résumé : On propose une construction effective d'algorithmes d'interpolation sur les courbes elliptiques définies sur F2 et F3 en utilisant des places de degrés > 1, avec une complexité bilinéaire minimale.


Antonella Perucca

jeudi 12 janvier
Antonella Perucca
(K.U. Leuven)
Caractérisations radicielles de courbes elliptiques

Webpage: https://perswww.kuleuven.be/~u0073281/


Jean-François Biasse

jeudi 5 janvier
Jean-François Biasse
(LIX, Palaiseau et Univ. Calgary)
Calcul du groupe de classes d'idéaux
et du groupe des unités d'un corps de nombres

Webpage: http://www.lix.polytechnique.fr/~biasse/

Résumé : Le calcul du groupe de classes d'idéaux ainsi que du groupe des unités d'un corps de nombres est une tâche majeure en théorie algorithmique des nombres. Cela permet notamment la résolution d'équation diophantiennes telles que les équations de Pell ou encore les équations de Thue. Au début des années 90, Buchmann a généralisé l'algorithm de Hafner et McCurley pour montrer que la complexité de ce problème était sous-exponentielle bornée par L(1/2,O(1)) dans les classes de corps de nombres de degré fixé.
Dans cette présentation, nous nous intéresserons aux derniers résultats, pratiques comme théoriques, sur le calcul du groupe de classes d'idéaux et du groupe des unités d'un corps de nombres. Nous nous pencherons en particulier sur les améliorations à l'algorithme du crible quadratique pour les corps de degré 2. Nous montrerons aussi comment généraliser cet algorithme aux corps de degré supérieur, puis nous discuterons de la possibilité d'atteindre une complexité bornée par L(1/3,O(1)) dans certaines classes de corps de nombres.

 

EL, le 26 novembre 2012