2010/2011

• 2011-05-26
  Jean-François Biasse (Calgary)
  Calcul du groupe de classes et des unités dans les corps de nombres
  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é (degré n plus petit que 10).
• 2011-05-19
  Lassina Dembelé (Warwick)
  Sur la conjecture de Gross
  Gross a conjecturé que pour tout premier p, il existe une extension finie de Q non-résoluble, non-ramifiée en dehors de p. (C'est maintenant un théorème.) Nous expliquerons comment les représentations galoisoisiennes associées aux formes de Hilbert mod p permettent une nouvelle approche de ce problème.
• 2011-05-05
  Andy Novocin (Lyon)
  L1 a new quasi-linear LLL algorithm
  The LLL lattice reduction algorithm of 1982 has proven to be useful in a wide variety of fields. It can be used to approximately solve computationally difficult lattice-based problems, such as the shortest vector problem, in polynomial time. We present a new algorithm for lattice reduction which is the first algorithm to have a complexity bound which is both polynomial and quasi-linear bound in the bit-length of the input. To achieve this we present an independently interesting toolkit for analyzing incremental lattice reductions.
• 2011-04-28
  Jérémy Le Borgne (Rennes)
  Algorithmique des phi-modules pour les représentations galoisiennes p-adiques
  Je présenterai quelques problèmes algorithmiques liés à l'étude des représentations galoisiennes p-adiques. J'expliquerai la correspondance entre certaines représentations p-adiques et des objets d'algèbre semi-linéaires appelés phi-modules. Je présenterai un algorithme polynomial pour déterminer certains invariants d'un phi- module, qui donnent des invariants équivalents sur la représentation associée, en particulier les poids de l'inertie modérée.
• 2011-04-14
  Vanessa Vitse (Versailles)
  Attaques par recouvrement et décomposition du logarithme discret sur courbes elliptiques.
  On présente dans cet exposé une méthode combinant la descente de Weil et les méthodes de calcul d'indices, qui permet d'attaquer le problème du logarithme discret sur courbes elliptiques définies sur des extensions de degré composé. En particulier, on donnera un exemple concret d'attaque du DLP pour un sous-groupe de taille 130 bits d'une courbe définie sur Fp⁶, a priori résistant à toute autre attaque connue.
• 2011-03-31
  Karim Belabas
  Termes restes dans le théorème de Davenport-Heilbronn III
• 2011-03-17
  Karim Belabas
  Termes restes dans le théorème de Davenport-Heilbronn II
• 2011-03-10
  Karim Belabas
  Termes restes dans le théorème de Davenport-Heilbronn I
• 2011-03-03
  Martin Weimann
  Factorisation torique des polynômes bivariés
  La plupart des algorithmes rapides actuels de factorisation des polynômes bivariés considèrent le degré total comme principal invariant. Quand le polynôme est creux, le degré se révèle être cependant un pauvre indicateur de complexité et on voudrait considérer des invariants plus fins. Dans cet exposé, je m'intéresse au polytope de Newton. Je prouve l'existence d'un algorithme déterministe qui, étant donné f ∈ Q[x, y] générique relativement à son polytope, et étant donnée la factorisation univariée de certains polynômes de facettes, calcule la factorisation rationnelle de f en petit temps polynomial en le volume du polytope. Quand le polynôme est suffisament creux, l'algorithme améliore considérablement les algorithmes denses les plus rapides (Chèze-Lecerf, Gao, Belabas-Van Hoeij-etc). La stratégie est de décomposer la courbe définie par f dans une compactification torique adéquate du plan affine. La preuve s'appuie alors sur un théorème d'extension des fibrés en droite, la théorie des résidus, la cohomologie des variétés toriques, et le critère d'irréductibilité de Ruppert.
• 2011-02-24
  Christophe Ritzenthaler
  Couplages sur les courbes d'Edwards et formules d'addition complètes
  Le modèle d'Edwards x²+y² =1+dx²y² des courbes elliptiques a connu un engouement important de la part de la communauté cryptographique, en particulier grâce à sa propriété de "complétude". Celle-ci exprime le fait qu'il existe une loi d'addition sur la courbe, valide pour tout couple de points rationnels dès lors que d n'est pas un carré dans le corps (alors que pour le modèle de Weierstrass, on utilise classiquement des expressions différentes suivant les cas – points distincts, doublement, addition du neutre...). Nous montrerons qu'une telle propriété peut se généraliser aux variétés abéliennes de toute dimension. Nous utiliserons pour cela la description des lois d'addition en termes de sections d'un certain fibré en droites. Ce travail est en collaboration avec Christophe Arène et David Kohel. Nous montrerons également comment on peut calculer efficacement le couplage de Tate sur le modèle d'Edwards (travail en collaboration avec Christophe Arène, Tanja Lange et Michael Naehring). Pour cela nous donnerons une description géométrique de la loi d'addition.
• 2011-02-17
  Nicolas Mascot
  Algorithmique pour les jacobiennes de courbes: algorithmes classiques et méthodes de Khuri-Maksidi
• 2011-02-10
  Jean-Marc Couveignes
  Géométrie des tangentes d'inflexion d'une cubique plane et les pseudo-paramétrisations qui s'en déduisent
• 2011-02-03
  Bill Allombert
  Calcul de points rationnels sur une courbe elliptique par la méthode de Silverman-Cremona-Delaunay.
  Soit E une courbe elliptique de rang analytique 1. La méthode de Silverman-Cremona-Delaunay permet de calculer explicitement un point rationnel sur E à l'aide du théorème de Gross-Zagier sur la hauteur des points de Heegner. L'éfficacité de la méthode dépend du choix de nombreux paramètres (choix d'une tordue quadratique de E, choix de représentants du groupe de classes sous l'action de certains groupes, etc.). Nous discutons de l'optimisation de ces paramètres, qui elle-même doit être faite efficacement.
• 2011-01-27
  Adrien Poteaux (Paris 6)
  Calculs rapides modulo un ensemble triangulaire et applications
  Soient F un corps parfait, et Y=(Y_1,…,Y_n) des indeterminees sur F. Un ensemble triangulaire (unitaire et en dimension 0) T=(T_1,…,T_n) est une famille de polynomes de F[Y] telle que pour tout i, T_i ∈ F[Y_1,...,Y_i] est unitaire et reduit modulo <T_1,…,T_{i-1}>. Le degré de T est le produit deg(T_1,Y_1)*...*deg(T_n,Y_n). Ces objets permettent de resoudre de nombreux problemes pour les systemes d'equations polynomiales. Cet exposé s'intéresse à la complexite de diverses operations modulo un ensemble triangulaire: la multiplication, l'inversion (quand cela est possible), calculer la norme de A ∈ F[Y]/<T>, le probleme de composition modulaire (i.e. calculer F(G_1(\Y),...,G_m(Y)) mod <T>) et le probleme transpose de projection des puissances, et enfin le probleme de changement d'ordre (sous certaines conditions). Nous decrirons pour ces problemes des algorithmes ayant une complexite binaire quasi-lineaire en la taille du probleme quand F est un corps fini, ce qui ameliore les algorithmes existants quand le nombre de variables n'est pas borné par une constante. Enfin, nous illustrerons brièvement une application de ces algorithmes dans le cas du problème de comptage de points des courbes elliptiques.
• 2010-12-17
  David Lubicz (Rennes)
  Couplage avec les fonctions thêta
  (in the Number Theory Seminar)
  Nous décrivons un algorithme de calcul de couplages utilisant les fonctions thêta. Puis nous revisitons divers techniques d'accélération de ces calculs (couplage de Ate, couplage optimal). Un bénéfice de notre approche est sa généralité puisqu'elle permet de calculer très naturellement des couplages sur toutes les variétés abéliennes. Nous obtenons aussi des gains de performance.

  Travail commun avec Damien Robert.

• 2010-12-17
  Vincent Verneuil
  Scalar multiplication on smart cards and side-channel analysis, le retour
• 2010-12-10
  Peter Bruin (Orsay)
  Sur le calcul des coefficients des formes modulaires
  (in the Number Theory Seminar)
  Soit f une forme modulaire de poids et niveau donnés sur un corps de nombres. Pour tout entier positif m, soit a_m(f) le m-ième coefficient du q-développement de f. On sait que f est déterminée par les coefficients a₀(f), ..., a_N(f), avec N suffisamment grand. Il est naturel de se poser la question si, étant donnés a₀(f), ..., a_N(f) et un entier positif m, on peut calculer «rapidement» a_m(f). J.-M. Couveignes, S. J. Edixhoven et al. ont récemment développé un algorithme pour résoudre ce probleme pour les formes de niveau 1. La méthode est basée sur le calcul de représentations modulaires de dimension 2 du groupe de Galois absolu de Q sur des corps finis. J'expliquerai cet algorithme, ainsi qu'une généralisation aux formes de plus haut niveau qui est donnée dans ma thèse. Je donnerai une application au problème suivant: pour k et n entiers, avec k pair, quel est le nombre de représentations de n comme somme de k carrés?
• 2010-12-10
  Xavier Roblot
  Zéros des fonctions L d'Artin p-adiques
  (in the AlgoL workshop)
• 2010-12-10
  Andreas Enge
  Polynômes de classes par restes chinois
  (in the AlgoL workshop)
• 2010-12-09
  Nicolas Mascot (École normale supérieure, Paris)
  Introduction à la méthode de Chabauty
  (in the AlgoL workshop)
• 2010-12-09
  Pascal Molin (CARAMEL, INRIA)
  Calcul numérique de valeurs de fonctions L
  (in the AlgoL workshop)
• 2010-12-09
  Jean-Marc Couveignes
  Zéros et variation de fonctions holomorphes
  (in the AlgoL workshop)
• 2010-12-09
  Marusia Rebolledo (Clermont-Ferrand)
  Points rationnels de courbes modulaires II: méthode de Mazur et points de Gross pour les petits niveaux
  (in the AlgoL workshop)
• 2010-12-09
  Pierre Parent
  Points rationnels de courbes modulaires I: estimations analytiques en grand niveau
  (in the AlgoL workshop)
• 2010-12-08
  Aurel Page (École normale supérieure, Paris)
  Calcul des domaines fondamentaux de groupes arithmétiques II
  (in the AlgoL workshop)
• 2010-12-08
  Damien Robert
  Variétés abéliennes, fonctions théta, applications II
  (in the AlgoL workshop)
• 2010-12-08
  Aurel Page (École normale supérieure, Paris)
  Calcul des domaines fondamentaux de groupes arithmétiques I
  (in the AlgoL workshop)
• 2010-12-08
  Damien Robert
  Variétés abéliennes, fonctions théta, applications I
  (in the AlgoL workshop)
• 2010-12-07
  Christophe Delaunay (Lyon)
  Non-zéros des séries L ∞-adiques
  (in the AlgoL workshop)
• 2010-12-07
  Guillaume Perbet (Besançon)
  Arithmétique et formules asymptotiques le long des extensions de Lie p-adiques
  (in the AlgoL workshop)
• 2010-12-07
  Henri Cohen
  Calcul de fonctions L de motifs hypergéométriques
  (in the AlgoL workshop)
• 2010-12-07
  Julien Blondeau (Besançon)
  Relèvement de représentations avec conditions en p
  (in the AlgoL workshop)
• 2010-12-06
  Peter Bruin (Orsay)
  Aspects computationnels des représentations galoisiennes modulaires
  (in the AlgoL workshop)
• 2010-12-06
  Bill Allombert
  Calcul de groupes d'inertie
  (in the AlgoL workshop)
• 2010-11-26
  Jean-Marc Couveignes
  Algorithmes quasi-optimaux: aussitôt dit, aussitôt fait
  (in the Number Theory Seminar)
  On apprend à l'école comment ajouter ou multiplier deux entiers. La division euclidienne et son application au calcul du PGCD viennent ensuite, et, plus tard, la multiplication des polynômes, puis des matrices. Pour chacun de ces problèmes, la méthode apprise à l'école est la plus facile à expliquer et la plus commode lorsque l'on traite des données de petite taille. Mais, d'un point de vue asymptotique, la méthode naïve n'est pas la meilleure, sauf pour l'addition. Pour multiplier deux nombres entiers, par exemple, il existe des algorithmes quasi-optimaux, c'est-à-dire des méthodes de calcul qui ne demandent pas (beaucoup) plus de temps qu'il n'en faut pour écrire le résultat. On ne peut donc espérer de meilleurs algorithmes. Ces méthodes de multiplication rapide utilisent la transformée de Fourier discrète. Inventées dans les années 1970, elles se sont répandues grâce à la micro-informatique et aux logiciels de calcul formel. Quant à la multiplication des matrices, Strassen et d'autres ont proposé depuis 1969 des méthodes théoriquement plus rapides que la méthode standard; mais on ignore s'il existe des algorithmes optimaux: multiplier deux matrices est aujourd'hui bien plus lent que de recopier le résultat. Majorer le rang du tenseur de multiplication des matrices est une question importante et difficile. Cohn et Umans on récemment reformulé cette question en termes de combinatoire et de représentations de groupes finis.

  Dans la première partie de mon exposé je présenterai quelques uns de ces problèmes importants de complexité algébrique.

  Je présenterai ensuite un travail commun avec Reynald Lercier, qui donne un algorithme quasi-optimal pour produire des polynômes irréductibles sur un corps fini, à l'aide de la théorie de Kummer des courbes elliptiques. La même question pour les entiers premiers reste ouverte.
• 2010-11-26
  Andreas Enge
  HQFRU HIDXW LODYR LUODE RQQHF OHI
  (in the INRIA Unithé ou Café seminar)
  Peut-on considérer la cryptologie, étymologiquement : la science du secret, comme une science à part entière? Sans doute que la réponse à cette question aurait été différente selon qu'elle ait été posée à l'Antiquité, durant la 2nde guerre mondiale ou encore hier...

  En effet, la cryptologie est à la fois un art ancien et une science nouvelle. Outil au service des puissants de ce monde très tôt, ce n'est un thème de recherche scientifique académique que depuis les années 1970.

  Nous allons nous intéresser plus particulièrement à la cryptographie, cette science de transformation des messages qui sert à en assurer la confidentialité, l'authenticité et l'intégrité. Elle est naturellement présente dans notre quotidien sans même que nous nous en rendions compte. Mais vous le découvrirez, en coulisses: c'est une quête vers les meilleurs niveaux de sécurité et les frontières sont sans cesse repoussées!
• 2010-11-19
  Pieter Rozenhart
  Computing quadratic function fields with high 3-rank via cubic field tabulation
• 2010-10-22
  Henri Cohen
  Fonctions L de motifs hypergéométriques II
• 2010-10-15
  Pascal Molin
  Intégration numérique et calculs de fonctions L
• 2010-10-12
  Damien Bernard
  Petits zéros de fonctions L associées à un corps quadratique imaginaire
  L'objet de cette étude est de mettre à l'épreuve la conjecture de densité de Katz et Sarnak sur la répartition des zéros de familles de fonctions L en regardant le cas des fonctions L associées à un corps quadratique imaginaire.
• 2010-10-12
  Manuel Charlemagne (Dublin)
  The security of the discrete logarithm problem (DLP) in the context of pairings
  When applying pairings in cryptographic protocols, it is important to ensure that the hardness of the DLP and ECDLP are equivalent in order to satisfy some given security requirements without compromising the efficiency of the computation. In this talk we explain how to achieve proper security levels and we also consider the less obvious problem of the minimum embedding field.
• 2010-10-07
  Paul Zimmermann (Nancy)
  Peut-on calculer sur ordinateur?
  (Leçon de Mathématiques d'aujourd'hui)
  Les calculs que l'on peut faire sur ordinateur se divisent en deux grandes classes: les calculs "exacts" (entiers, entiers modulo n, rationnels, ...) et les calculs "inexacts" (nombres à virgule fixe ou flottante, nombres p-adiques, ...) On s'intéresse plus particulièrement dans cette leçon aux nombres à virgule flottante, aussi appelés "nombres flottants". Les calculs flottants étant inexacts, peut-on en tirer une information rigoureuse, que l'on peut utiliser dans la preuve d'un théorème? Par exemple, comment prouver π < 22/7 à l'aide d'un ordinateur? Peut-on obtenir dix décimales significatives de l'intégrale entre x=17 et x=42 de la fonction exp(-x²) log(x)? On commencera par rappeler quelques "catastrophes" dues à une mauvaise prise en compte des erreurs inhérentes au calcul flottant. On évoquera ensuite plusieurs méthodologies qui permettent d'obtenir une information rigoureuse sur le résultat d'un calcul flottant (arrondi correct, arithmétique d'intervalles, modèle RealRAM, ...) et on indiquera quelques outils logiciels qui implantent ces méthodologies. Enfin, on illustrera la leçon par l'exemple du calcul de la deuxième décimale de la constante de Masser-Gramain (travail en cours avec Guillaume Melquiond).
• 2010-10-01
  Vincent Verneuil
  Scalar multiplication on smart cards and side-channel analysis
  Scalar multiplication is the main operation of Elliptic Curve Cryptography. Its implementation on smart cards in an industrial context requires much effort in order to satisfy performance and security goals. Indeed short timing execution are required in many applications and must be achieved given the power and memory constraints of the smart cards. On the other hand the well known side- channel analysis can threaten the secrets manipulated by the card, such as secret scalars. Therefore numerous studies have proposed solutions for speeding-up the elliptic curve scalar multiplication and counterfeiting side-channel attacks. Not all of these solutions fit to the industrial smart card context however.
• 2010-09-24
  Michael Drmota (Wien)
  An asymptotic analysis of Cuckoo hashing
  The aim of this talk is to present a recent hash algorithm, which is called Cuckoo Hashing, and to provide a precise asymptotic analysis. Cuckoo Hashing has been introduced by Pagh and Rodler in 2001 and has (by construction) constant worst case search time and also a very good performance in conflict resolution. The analysis of standard Cuckoo Hashing that we present here rests on a generating function approach to the so called Cuckoo Graph, a random bipartite graph. With help of double saddle point methods (and related techniques) it will be shown that the probability that the construction of a hash table succeeds, is asymptotically 1-c(ε)/m+O(1/m²) for some explicit c(ε), where m denotes the size of each of the two tables, n=m(1-ε) is the number of keys and 0 < ε < 1. Further we show that the expected running time is linear. The talk is based on joint work with Reinhard Kutzelnigg.
• 2010-09-17
  Henri Cohen
  Fonctions L de motifs hypergéométriques I
• 2010-09-09
  Jean-François Biasse
  Subexponential algorithms for number fields