2011/2012

• 2012-07-02
  Bernhard Schmidt (Singapore)
  Values and ideals in combinatorial problems
  The absolute value of complex numbers is surprisingly useful in the investigation of certain combinatorial problems. The connection usually arises from embedding finite cyclic groups into the complex numbers by sending the group elements to roots of unity. The absolute value of the resulting sums of roots of unity, i.e., cyclotomic integers, usually is known explicitly, which allows the application of two powerful tools: the ideal theory of algebraic numbers and “size arguments” involving the absolute value of complex numbers. We will present some highlights of this approach including recent progress on circulant Hadamard matrices, Barker sequences, and the structure of circulant weighing matrices.
• 2012-06-14
  Bruno Salvy
  Itération de Newton: du numérique à la combinatoire, et réciproquement
  (in the Colloquium)
  L'efficacité d'un grand nombre d'algorithmes anciens ou récents repose sur la convergence rapide de l'itération de Newton. Numériquement, et suffisamment près de la solution, le nombre de chiffres corrects double à chaque itération. Pour des séries formelles, le problème de choisir un bon point initial disparaît et c'est le nombre de coefficients corrects qui est doublé à chaque itération. Cette observation, couplée à la multiplication rapide, mène à des algorithmes rapides pour de nombreuses questions de calcul formel, allant de résultats classiques sur les séries algébriques jusqu'à de plus récents pour les systèmes d'équations différentielles. L'itération de Newton peut être remontée plus encore à un niveau combinatoire. Dans ce cadre, la convergence quadratique s'interprète comme l'augmentation du nombre de Strahler. Cette itération combinatoire se traduit en une itération efficace au niveau des séries génératrices et fournit un algorithme efficace pour l'énumération combinatoire. Ceci améliore l' efficacité de la génération aléatoire par une technique connue sous le nom de méthode récursive. De plus, l'évaluation numérique de cette itération mène à un algorithme numérique rapide qui était le chaînon manquant pour la génération aléatoire efficace par la méthode de Boltzmann, de sorte que des objets aléatoires de très grande taille peuvent maintenant être produits automatiquement. Il s'agit d'un travail en commun avec Carine Pivoteau et Michèle Soria.
• 2012-06-13
  Vincent Verneuil
  Cryptographie à base de courbes elliptiques et sécurité de composants embarqués
  (doctoral defense)
• 2012-05-24
  Pierre Lezowski
  Corps de quaternions euclidiens
  Soient K un corps de nombres, F un corps de quaternions sur K et O un ordre de F. Nous présenterons des techniques pour étudier l'euclidianité de O, par rapport à la norme ou un stathme quelconque. En nous appuyant sur la construction de Motzkin, nous étudierons le cas particulier où F est totalement défini quand K est le corps des rationnels ou un corps quadratique.

  Il s'agit d'un travail en commun avec Jean-Paul Cerri et Jérôme Chaubert.

• 2012-05-10
  Damien Robert
  Polynômes de classes en genre 2 par la méthode des restes chinois
• 2012-04-12
  Gaëtan Bisson (Sydney)
  Un algorithme à la Pollard pour le problème du sac à dos
  Soit S une suite finie d'éléments d'un groupe fini G noté multiplicativement ; le problème du sac à dos consiste à trouver une sous-suite de S dont le produit vaut un élément donné z de G. Pour certains groupes particuliers comme G=Z/nZ, on connait des méthodes très efficaces pour le résoudre ; cependant, aucun algorithme générique ne peut résoudre ce problème en moins de O(sqrt(#G)) opérations.

  Une approche de type « pas de bébé, pas de géant » atteint cette complexité en temps mais requiert un espace mémoire de taille comparable. La première partie de cet exposé présentera une adaptation d'idées de Pollard à ce contexte afin d'obtenir un algorithme similaire mais au coût mémoire négligeable. Ensuite, j'en présenterai certaines applications, notamment au calcul d'isogénies entre deux courbes elliptiques.

  Ces travaux sont conjoints avec Andrew V. Sutherland.

• 2012-03-29
  Marco Streng (Warwick)
  Smaller class invariants for quartic CM-fields
  The theory of complex multiplication allows one to construct elliptic curves with a given number of points. The idea is to construct a curve over a finite field by starting with a special curve E in characteristic 0, and taking the reduction of E modulo a prime number.

  Instead of writing down equations for the curve E, one only needs the minimal polynomial of its j-invariant, called a Hilbert class polynomial. The coefficients of these polynomials tend to be very large, so in practice, one replaces the j-invariant by alternative class invariants. Such smaller class invariants can be found and studied using an explicit version of Shimura's reciprocity law.

  The theory of complex multiplication has been generalized to curves of higher genus, but up to now, no class invariants were known in this higher-dimensional setting. I will show how to find smaller class invariants using a higher-dimensional version of Shimura's reciprocity law.

• 2012-03-22
  Henri Cohen
  Lacunarité des quotients η
• 2012-03-12
  Vasily Golyshev
  Searching for congruences of Galois representations
  The famous theorem of Ramanujan states that Δ = q Π (1-qⁱ)24 = Σ a_i qⁱ has the congruence property a_p = p¹¹+1 mod 691 for any prime p. In modern language, it says that the two-dimensional modular representation Φ that corresponds to Δ is congruent to an extension of a character by a character mod 691: Φ = char + char mod 691 at the level of semisimplifications. Another example of such behavior, albeit of a different nature, is an elliptic curve X₀(11): the existence of a 5-torsion rational point on it leads to the congruence a_p=1+p mod 5.

  We are interested in 4-dimensional Galois representations Ψ of weight 3 that arise in Calabi-Yau threefolds. An intuition says that a phenomenon of bi-congruence may exist, namely, for certain Ψ there would be a pair of moduli (N₁, N₂) and two rank 2 Galois representations Φ₁, Φ₂ such that, at the level of semisimplifications, or trace functions, Ψ = Φ₁ + char + char mod N₁ and Ψ = Φ₂ +char + char mod N₂.

  We will discuss computational approaches to the problem of the existence of Calabi-Yau Galois representations with bi-congruences.

• 2012-03-09
  Damien Stehlé (Lyon)
  Une preuve de sécurité pour le cryptosystème NTRU
  (in the Number Theory Seminar)
  NTRUEncrypt, proposé en 1996 par Hoffstein, Pipher et Silverman, est le schéma de chiffrement asymétrique le plus efficace, parmi ceux dont la sécurité repose sur la difficulté de problèmes portant sur les réseaux euclidiens. Malheureusement, depuis sa création, sa sécurité a régulièrement été mise en doute. Nous montrerons comment modifier NTRUEncrypt pour qu'il admette une preuve de sécurité contre les attaques à clair choisi, sous l'hypothèse qu'il est difficile de trouver des vecteurs courts dans des réseaux correspondant à des idéaux arbitraires des anneaux d'entiers de corps cyclotomiques. La preuve repose sur les travaux récents de [Lyubashevsky et al., Eurocrypt'10] sur la difficulté du problème Ring-LWE. Notre principale contribution est de démontrer que si les polynômes de petites hauteurs correspondant à la clé secrète sont tirés suivant une loi Gaussienne discrète, alors la distribution de la clé publique, qui est leur quotient modulo un entier, est statistiquement proche de la loi uniforme sur son domaine.

  Travail en commun avec Ron Steinfeld

• 2012-03-08
  Jean-Marc Couveignes
  Logarithmes discrets elliptiques par recouvrement II
• 2012-02-24
  Jean-Marc Couveignes
  Logarithmes discrets elliptiques par recouvrement I
• 2012-02-02
  Vincent Verneuil
  Square Always Exponentiation
  Embedded exponentiation techniques have become a key concern for security and efficiency in hardware devices using public key cryptography. An exponentiation is basically a sequence of multiplications and squarings, but this sequence may reveal exponent bits to an attacker on an unprotected implementation. Although this subject has been covered for years, we present in this paper new exponentiation algorithms based on trading multiplications for squarings. Our method circumvents attacks aimed at distinguishing squarings from multiplications at a lower cost than previous techniques. Last but not least, we present new algorithms using two parallel squaring blocks which provide the fastest exponentiation to our knowledge.
• 2012-01-27
  Bill Allombert
  PARI's floating point kernel
  (in Atelier PARI/GP 2012)
• 2012-01-27
  Loïc Grenié
  bnfinit()
  (in Atelier PARI/GP 2012)
• 2012-01-27
  Aurel Page
  Quaternion algebras
  (in Atelier PARI/GP 2012)
• 2012-01-26
  Loïc Grenié
  A modular HNF
  (in Atelier PARI/GP 2012)
• 2012-01-26
  Bill Allombert
  Parallel programming
  (in Atelier PARI/GP 2012)
• 2012-01-25
  Bill Allombert
  Error trapping / t_ERROR
  (in Atelier PARI/GP 2012)
• 2012-01-25
  Charles Boyd (University of Massachusets Amherst)
  Paridroid
  (in Atelier PARI/GP 2012)
• 2012-01-24
  Bill Allombert
  gp2c & clean GP programming
  (in Atelier PARI/GP 2012)
• 2012-01-24
  Karim Belabas
  Contributing a new function; documentation, test
  (in Atelier PARI/GP 2012)
• 2012-01-23
  Karim Belabas
  The PARI source code; navigation, debugging
  (in Atelier PARI/GP 2012)
• 2012-01-23
  Bill Allombert
  Git+PARI
  (in Atelier PARI/GP 2012)
• 2011-12-01
  Athanasios Angelakis
  Isomorphic Absolute Galois Groups of Number Fields
  By the Neukirch-Uchida theorem, two number fields K and K' are isomorphic if and only if their absolute Galois groups are. It is possible for non-isomorphic number fields to have isomorphic absolute abelian Galois groups. In the case of imaginary quadratic fields, class field theory enables us to describe these abelian Galois groups and to construct examples where they are isomorphic.
• 2011-10-25
  Karim Belabas
  Développer avec et pour Pari/Gp
• 2011-10-25
  Bill Allombert
  Développement de Pari/Gp sous Git
  Une séance de travaux pratiques qui couvrira les sujets suivants:

  • les concepts de base du contrôle de version avec git;
  • comment rester à jour des derniers développements de pari/gp;
  • comment contribuer au développement.
• 2011-10-13
  Julio Brau
  Computing the image of Galois representations attached to elliptic curves
  I will discuss ongoing work on an algorithm that computes the full image of the Galois representation attached to an elliptic curve.
• 2011-10-05
  Michael Rubinstein (Waterloo)
  Conjectures, experiments, and algorithms concerning the moments of L(1/2,χ_d)
  I'll report on some extensive computations with Matthew Alderson in which we computed the values of L(1/2, χ_d) for -5·10¹⁰≤d≤ 1.3·10¹⁰ in order to test conjectures concerning the moments ∑_{|d| < X} L(1/2, χ_d)^k. Specifically we were interested in testing the full asymptotics for the moments conjectured by Conrey, Farmer, Keating, Rubinstein, and Snaith, as well as the conjecture of Diaconu, Goldfeld, and Hoffstein concerning additional lower terms in the moments. I'll also describe the algorithms we used for this large computation.
• 2011-09-30
  Damien Robert
  Couplages optimaux sur variétés abéliennes via les fonctions thêta
  (in the Number Theory Seminar)
  L'utilisation de couplages en cryptographie a connu un grand essor ces dernières années, car elle permet la réalisation de protocoles comme la cryptographie basée sur l'identité, de manière efficace. Pour l'instant, les seuls couplages cryptographiquement sûrs connus viennent des variétés abéliennes. L'algorithme de Miller permet de calculer efficacement le couplage de Weil et de Tate sur les Jacobiennes de courbes hyperelliptiques. Une collaboration avec David Lubicz nous a permis de développer un algorithme pour calculer le couplage sur une variété abélienne par le biais des fonctions thêta. Pour des raisons d'efficacité, des modifications du couplage de Tate ont été développées dans le cadre des courbes elliptiques (couplage de ate optimal). Dans cet exposé, nous décrirons notre algorithme, et comment l'adapter aux couplages optimaux. Il s'agit d'une collaboration avec David Lubicz.
• 2011-09-28
  Peter Stevenhagen (Leiden)
  Radical extensions and primitive roots
  It follows from the work of Artin (1927, 1958) and Hooley (1967) that, under assumption of the generalized Riemann hypothesis, every non-square rational number different from -1 is a primitive root modulo infinitely many primes. Moreover, the set of these primes has a natural density that can be written as the product of a `naive density' and a somewhat complicated correction factor reflecting the entanglement of the radical extensions from which the density statement is obtained. We show how the correction factors arising in Artin's original primitive root problem and the many generalizations that have been studied in the last few decades can be interpreted as character sums describing the nature of the entanglement. The resulting description in terms of local contributions is so transparent that it greatly facilitates explicit computations.

  This is joint work with Hendrik Lenstra and Pieter Moree.

• 2011-09-23
  Jean-Marc Couveignes
  Paramétrisation des cubiques planes à l'aide d'un radical cubique
  (in the Number Theory Seminar)
  Étant donnée une cubique lisse projective plane C sur un corps K de caractéristique première à 6, on cherche des morphismes finis f : D→C où D est un revêtement radiciel de P1/K de degré 3. On dit que f est une paramétrisation de C à l'aide d'un radical cubique. Ces paramétrisations présentent un intérêt cryptographique. Icart, Kammerer, Lercier, Renault and Farashahi en ont donné quelques exemples. J'expliquerai pourquoi ces paramétrisations correspondent à des courbes rationnelles dans le plan dual, ayant des propriétés remarquables d'intersection avec la duale Ĉ de C. De telles courbes se relèvent en des courbes rationnelles sur le revêtement de degré 2 du plan dual ramifié le long de Ĉ. Ce revêtement est une surface K3 de rang générique 19. L'étude de son groupe de Néron-Séveri met de l'ordre dans les paramétrisations connues et permet d'en produire de nouvelles.

  Travail en commun avec Jean-Gabriel Kammerer.

• 2011-09-07
  Jérôme Milan
  Pairings implementation in the PARI computer algebra system
  Pairing-based cryptography has been one of the most active areas in asymmetric cryptology in the past two decades. They were initially introduced with the destructive goal of transferring the resolution of the discrete logarithm problem from elliptic curves to finite fields. However, the last decade saw the explosion of the use of pairings with constructive objectives such as identity-based cryptography or short signatures, and a great amount of effort was invested to speed up their computations. In this presentation, I will report on the design of a PARI/GP module for computing pairings on elliptic curves over large characteristic fields. The definition of the Tate, Weil and ate pairings will be recalled, together with the notion of optimal pairing independently proposed by Hess and Vercauteren. Most pairings consist of the evaluation of a rational function followed by an exponentiation in a large finite field. We will explain both steps and describe some recent improvements found in the literature. The remainder of the talk will deal with our implementation in PARI/GP: available algorithms, weaknesses of our implementation, and benchmarks.