Institut de Mathématiques de Luminy

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


Responsables: G. Lachaud, F. Rodier
Horaires: Le jeudi à 14h30
Salle: amphi du 1er étage, salle 130-134, I.M.L., Groupe des Laboratoires de Luminy (CNRS).

Planning

jeudi 16 décembre
Massimiliano Sala
(Université de Trente)
On the first and second weight of codes
from Hermitian curves


Homepage: http://www.science.unitn.it/~sala/

Abstract: The codes from Hermitian curves are probably the class of one-point AG codes that has been studied more deeply. For any finite field, these codes can be grouped in four classes, depending on the relation between their dimension and their distance. Although the distance is known for all classes, the number of minimum-weight codewords is still unknown.
In this talk we present joint work with Marco Pellegrini and Chiara Marcolla, where we determine for one class (i.e, for $d\leq q$) both the number of words with weight d and the number of words with weight d+1. Our result comes from an unexpected geometric relation on the points forming small weight codewords.


jeudi 9 décembre
Alexandre Venelli
(IML, Marseille)
Algorithmes de multiplication scalaire
réguliers et efficaces



Marc-Hubert Nicole

jeudi 2 décembre
Marc-Hubert Nicole
(IML, Marseille)
Un invariant de Hasse-Witt pour les courbes de Shimura en les caractéristiques divisant le discriminant


page web : http://iml.univ-mrs.fr/~nicole/

Résumé : Soit E une courbe elliptique sur un corps de caractéristique p>0. L'invariant de Hasse est une forme modulaire modulo p, et vit donc naturellement sur une courbe modulaire. Quand cet invariant de Hasse est nul, on dit que la courbe E est supersingulière; sinon, elle est dite ordinaire.
Remplaçons la courbe modulaire par une courbe de Shimura. Il arrive parfois que son lieu ordinaire soit entièrement vide, et nous sommes alors dans la situation un brin fâcheuse où l'invariant de Hasse est nul sur toute la courbe! Nous proposerons dans cet exposé une solution de remplacement.


Stéphane Louboutin

jeudi 25 novembre
Stéphane Louboutin
(IML, Marseille)
Unités fondamentales des ordres
engendrés par une unit
é


page web : http://iml.univ-mrs.fr/~loubouti/

Résumé : Si $\epsilon$ est une unité algébrique pour lequel le rang du groupe des unités de l'ordre ${\bf Z}[\epsilon]$ est égal à $1$, nous esquissons une preuve de ce que $\epsilon$ est (sauf exceptions) une unité fondamentale de cet ordre ${\bf Z}[\epsilon]$.
Nous envisageons ensuite le cas où le rang du groupe des unités de l'ordre ${\bf Z}[\epsilon]$ est égal à 2 et prouvons dans ce cas un résultat presqu'aussi satisfaisant que le précédent.


Philippe Langevin

jeudi 18 novembre
Philippe Langevin
(Univ. Toulon)
A propos d'une conjecture de Helleseth


page web : http://langevin.univ-tln.fr/

Résumé : L'objectif de mon exposé est de présenter différents aspects d'une conjecture formulée par Tor Helleseth dans les années 70. En quelques mots :
- K un corps fini d'ordre q de caractéristique 2
- X le caractère additif canonique de K
- d un entier premier avec q - 1
La conjecture de Helleseth affirme l'existence d'un élément non nul a de K tel que la somme de caractères sum_{x dans K } X( f( x ) + a x) s'annule.


Mehdi Tibouchi

jeudi 4 novembre
Mehdi Tibouchi
(ENS Paris)
Fonctions de hachage à valeur
dans les courbes (hyper)elliptique


homepage : http://www.di.ens.fr/~tibouchi/

Voir le preprint : http://www.ma.utexas.edu/users/voloch/Preprints/welldistributed.pdf
où on utilise une version des conjectures de Weil pour les fonctions L sur les courbes pour établir des résultats de régularité.


jeudi 14 octobre
Jean-Pierre Flori
(Telecom ParisTech)
Quelques résultats à propos d'une conjecture
sur la distribution des chaînes binaires


page web : http://www.infres.enst.fr/wp/mic2/carte-de-visite/?idpers=532&basepermanents=on&inputgroupes=0&inputfotos=on

Résumé : Il est difficile de construire des fonctions booléennes satisfaisant tous les critères nécessaires pour une utilisation en cryptographie symétrique.
Dans un article récent, Tu et Deng ont proposé une famille infinie de fonctions booléennes qui ont d'intéressantes propriétés à condition qu'une conjecture de nature combinatoire soit vérifiée.
Il s'agit de démontrer que pour tout entier k et tout entier modulaire t, le cardinal de l'ensemble suivant :
{(a,b) mod (2^k) - 1 : a+b = t , w_H(a)+w_H(b) < k} est plus petit que 2^(k-1) (w_H est le poids de Hamming).
Dans cet exposé, nous mettrons en évidence l'importance du nombre de retenues qui se produisent lors de l'addition modulaire.
En ajoutant des hypothèses sur la forme de t, nous démontrerons ensuite la conjecture dans des cas simples et asymptotiques.
Enfin, nous exhiberons une famille d'entiers qui atteignent la borne de la conjecture et qui semblent être les seuls à le faire.


jeudi 24 juin
Cédric Pépin
(IMB, Bordeaux)
Dualité et réduction des jacobiennes


page web : http://www.math.u-bordeaux1.fr/maths/spip.php?article43&uid=pepin

Résumé : Soient A une variété abélienne sur un corps de valuation discrète à corps résiduel parfait, et A' sa variété abélienne duale. Pour comprendre comment la dualité entre A et A' se comporte au niveau de leurs modèles de Néron, Grothendieck a introduit un accouplement entre les groupes de composantes de ces modèles. Cet accouplement est conjecturé parfait, et cette conjecture a été démontrée dans de nombreux cas. Dans cet exposé, nous nous intéresserons plus particulièrement au cas où A est la jacobienne d'une courbe C. Grâce à la théorie des symboles de Néron, Bosch et Lorenzini ont prouvé la conjecture lorsque C possède un point rationnel. Après avoir rappelé leur méthode, nous expliquerons quelques techniques permettant de travailler lorsque C n'a pas de point rationnel.


Michael Pohst

jeudi 17 juin
Michael Pohst
(Institut für Mathematik, Berlin)
Computation of integral points of a Mordell curve (y^2=x^3+k) over global fields


homepage : http://www.math.tu-berlin.de/~pohst/

Abstract: In his 1997 thesis K. Wildanger developed an efficient method for computing such points over the rational integers. We improve and generalize his ideas. Replacing his methods from the geometry of numbers by a class field theoretic approach based on Hasse we get a much more powerful algorithm. (This is a report on work in progress).


jeudi 10 juin
Julia Pieltant
(IML, Marseille)
Une amélioration des bornes de la complexité bilinéaire de la multiplication dans toute extension de F_2

Résumé : La multiplication dans les corps finis est un problème central en cryptographie et en théorie des codes : l’efficacité de la multiplication influe sur la rapidité du chiffrement et du déchiffrement mais aussi sur celle des différentes méthodes de décodage. C’est pourquoi, dans les 30 dernières années, un intérêt considérable a été porté au problème de la détermination de sa complexité, c’est-à-dire du nombre d’opérations élémentaires dans F_q nécessaires pour calculer le produit de deux éléments de F_{q^n}.
On distingue en fait deux types d’opérations élémentaires : les opérations scalaires (additions, multiplications par des constantes) comptabilisées par la complexité scalaire et les opérations bilinéaires (multiplications de deux éléments de F_qdépendants directement des éléments de F_{q^n} dont on effectue le produit) comptabilisées par la complexité bilinéaire. Ce dernier type de complexité est indépendant de la base de F_{q^n} sur F_q choisie et est de plus relié au problème de la détermination du rang de tenseur.
Au cours de exposé, on se propose de présenter l'algorithme de type Chudnovsky, qui est actuellement le meilleur algorithme de multiplication connu en terme de complexité bilinéaire, ainsi qu'une amélioration de cet algorithme présentée indépendamment par Arnaud et Cenk - Özbudak. On utilisera ensuite cet algorithme avec des places de degré 1, 2 et 4 sur la tour de corps de fonctions algébriques de Garcia - Stichtenoth descendue sur F_2 afin d'obtenir de nouvelles bornes pour le rang de tenseur de la multiplication dans toute extension de F_2. En particulier, cela nous permettra d'établir la meilleure borne asymptotique connue.


jeudi 27 mai
Michel Laurent
(IML, Marseille)
Exposants de densité d'orbites planes



Nicolas Ratazzi

jeudi 6 mai
Nicolas Ratazzi
(Université Paris-Sud)
Borne sur la torsion pour les variétés abéliennes


Page web : http://www.math.u-psud.fr/~ratazzi/

Résumé : Soit A une variété abélienne définie sur un corps de nombres K. Le nombre de points de torsion définis sur une extension finie L est borné polynomialement en terme du degré [L:K]. Lorsque A est isogène à un produit de variétés abéliennes simples de type GSp, c'est-à-dire dont le groupe de Mumford-Tate est "générique" (isomorphe au groupe des similitudes symplectiques) et vérifiant la conjecture de Mumford-Tate, nous calculons l'exposant optimal dans cette borne, en terme de la dimension des sous-variétés abéliennes de A. Le résultat est inconditionnel pour un produit de variétés abéliennes simples dont l'anneau d'endomorphismes est l'anneau entiers rationnels Z et dont la dimension n'appartient pas à un ensemble exceptionnel explicite S={4,10,16,32,...}. Après des rappels nécessaires sur les différents objets en jeu (variétés abéliennes, représentations l-adiques associées à l'action de Galois sur les points de torsion...) je donnerai une preuve du résultat pour une courbe elliptique sans CM et une esquisse de preuve dans le cas général.


Nadia El Mrabet

jeudi 1er avril
Nadia El Mrabet
(LIRMM, Montpellier)
Arithmétique des couplages, performance
et résistance aux attaques par canaux cachés

Résumé : Mes travaux portent sur l'étude des couplages, et plus particulièrement leur utilisation en cryptographie. Mes premiers travaux ont portés sur l'arithmétique des couplages à travers une comparaison des complexités en nombre d'opérations des couplages de Weil et Tate. Puis je me suis intéressée à l'étude de l'arithmétique utile pour les couplages. Un de mes travaux propose d'utiliser une représentation alternative des corps finis pour améliorer l'efficacité des calculs impliqués dans les couplages. Le second étudie en détail l'arithmétique des couplages pour les courbes dont le degré de plongement est 15. Ces premiers travaux m'ont permis de me familiariser avec les couplages et je me suis alors orientée vers la résistance aux attaques par canaux cachés des algorithmes de couplage. J'ai étudié les faiblesses de l'algorithme de Miller soumis à des attaques par analyse de consommation de courant et par injection de fautes.


Regis Blache

jeudi 25 mars
Régis Blache
(UAG, Guadeloupe)
Étude p-adique des sommes de caractères

Résumé : Le premier résultat sur les valuations de sommes de caractères est le théorème de Stickelberger sur les sommes de Gauss. Depuis on n'a cessé d'améliorer ces résultats, en particulier en lien avec les théorèmes du type Chevalley-Warning sur le nombre de points des variétés sur les corps finis, ou avec des applications en théorie de l'information (fonctions booléennes non linéaires par exemple).
On présentera une autre amélioration, qu'on reliera avec le polygone de Newton des courbes d'Artin-Schreier (les revêtements cycliques d'ordre p de la droite projective en caractéristique p, qui sont des courbes hyperelliptiques en caractéristique 2).
Il est bien connu que ces courbes fournissent des exemples de polygones de Newton éloignés du "polygone ordinaire" (ayant deux segments, de pentes respectives 0 et 1). On donnera alors quelques résultats, très partiels, sur la stratification de l'espace de ces courbes par leur polygone de Newton. On étudiera plus particulièrement les courbes de petit genre en caractéristique 2 et les courbes supersingulières.


Leo Storme

jeudi 18 mars
Leo Storme
(Ghent University)
Linear codes arising from finite incidence structures

Abstract: Consider the finite projective space PG(N, q) of dimension N over the finite field Fq of order q. Via the incidence matrices of points and k-spaces of PG(N,q), it is possible to define the generator matrix of a linear code C, and the parity check matrix of its dual linear code C⊥.
This linear code is of interest from a coding-theoretical point of view, but it is also of interest from a geometrical point of view. Some of the best geometrical results are obtained by making use of this linear code C.
In recent years, there has been a new incentive in the study of these linear codes and their dual linear codes. Many new results on the small weight codewords of these linear codes and their dual linear codes have been obtained.
In this talk, I present a number of these new results, and also give a geometrical result obtained by using these linear codes.


jeudi 4 mars
David Kohel
(IML, Marseille)
Construction de surfaces abéliennes avec multiplications réelles ou complexes

Abstract: The use of abelian surfaces (generally constructed as a Jacobian of a genus 2 hyperelliptic curve) in cryptography is limited by the availability of efficient point counting algorithms. Good algorithms exist for small characteristic (using p-adic cohomology and/or deformation) or for large characteristic via explicit CM constructions.
The CM method in cryptography uses complex multiplication of abelian varieties to determine the number of points, up to a finite set of possibilities, from the moduli for a given endomorphism ring. We recall the state of the art for the CM method in dimension 2, including complex analytic and p-adic methods, and variants using alternative invariants.
The use of moduli for real multiplication (in dim > 1) is less well treated in cryptographic applications. We describe analogous problems for construction of the RM surfaces in dimension 2 RM moduli surfaces, and recent work to exploit explicit real multiplication in the point counting problem in large characteristic.


jeudi 25 février
Marc Girault
(Expert, Caen)
Cryptologie et courbes elliptiques :
une love (?) story de 25 ans

Abstract: 1984: a new factoring method emerges from H.W. Lenstra's brain, "...derived from the Pollard p-1-method by replacing the multiplicative group by a random elliptic curve". The algorithm is published in 1985, followed some months later by Miller and Koblitz, indepedently fitting discrete-logarithm-based schemes (including Diffie-Hellman and El-Gamal) to this new paradigm : ECC is born. Since that time, considerable attention has been turned by researchers to this area, which appears today as a credible alternative to factoring-based public-key algorithms such as RSA - even if, for the moment, it failed in superseding it. In this talk, we try to tell the 25-year love (?) story between cryptology and elliptic curves, by positioning it in the more global context of modern cryptology.


Robert Rolland

jeudi 4 février
Robert Rolland
(IML, Marseille)
À propos d'un théorème de Yao
sur les générateurs pseudo-aléatoires

Page web : http://robert.rolland.acrypta.com/

Résumé : Le théorème de Yao énonce l'équivalence, dans le contexte d'une étude de la complexité asymptotique des algorithmes probabilistes polynomiaux utilisés, entre l'indistinguabilité et l'inprévisibilité du prochain bit des générateurs pseudo-aléatoires.
Nous présentons ici une version non asymptotique, qui permet de se placer dans le cas de générateurs de taille fixée. Nous calculons les coûts des réductions d'un algorithme à l'autre. Nous en déduisons un exposé complet d'une généralisation du théorème dans le cas asymptotique.


David Kohel

jeudi 28 janvier
David Kohel

(IML, Marseille)
Construction de surfaces abéliennes
avec multiplications réelles ou complexes

Page web : http://iml.univ-mrs.fr/~kohel/


jeudi 21 janvier
Didier Alquié

(DGA-CELAR, Rennes)

L'addition dans Z et dans F2
ou "Approximation de l'addition par le XOR :
comment aller (un peu) plus loin que P. Sarkar"

resume alquie 2010


EL, le 8 novembre 2010