Publications of Pierrick Gaudry

Warning: this page is no longer maintained.

You can browse my publications on Hal.

Refereed journal papers

  • An extension of Satoh's algorithm and its implementation, M. Fouquet, P. Gaudry and R. Harley. J. Ramanujan Math. Soc. 15 (2000), 281-318.
  • Constructive and destructive facets of Weil descent on elliptic curves, P. Gaudry, F. Hess and N. Smart. J. of Cryptology 15 (2002), 19-46.
  • A general framework for subexponential discrete logarithm algorithms, A. Enge and P. Gaudry. Acta Arith. 102 (2002), 83-103.
  • Counting points in medium characteristic using Kedlaya's algorithm, P. Gaudry and N. Gürel. Experimental Math. 12 (2003), 395--402.
  • Modular equations for hyperelliptic curves, P. Gaudry and É. Schost. Math. Comp. 74 (2005), 429--454. The modular equation of degree 3 and genus 2 can be downloaded here.
  • Evaluation properties of symmetric polynomials, P. Gaudry, N. M. Thiéry and É. Schost. Internat. J. Algebra Comput. 16 (2006), 505--523.
  • A double large prime variation for small genus hyperelliptic index calculus, P. Gaudry, E. Thomé, N. Thériault and C. Diem. Math. Comp. 76 (2007), 475--492. (note that contrary to what is claimed by AMS, this paper is in public domain.)
  • Linear recurrences with polynomial coefficients and application to integer factorization and Cartier-Manin operator, A. Bostan, P. Gaudry and É. Schost. SIAM J. Comput. 36 (2007), 1777--1806.
  • (Satiric) Secure H-numbers, P. Gaudry. J. Craptology 3 (2006).
  • Fast genus 2 arithmetic based on Theta functions, P. Gaudry. Journal of Mathematical Cryptology 1 (2007), 243-265.
  • Index calculus for abelian varieties and the elliptic curve discrete logarithm problem , P. Gaudry. J. Symbolic Comput. 44 (2009), 1690-1702.
  • The arithmetic of characteristic 2 Kummer surfaces and of elliptic Kummer lines, P Gaudry and D. Lubicz. Finite Fields and Their Applications 15 (2009), 246-260.
  • An L(1/3) discrete logarithm algorithm for low degree curves, A. Enge, P. Gaudry and E. Thomé. To appear in J. Cryptology, 2010.
  • Algorithmes de comptage de points d'une courbe définie sur un corps fini, P. Gaudry. To appear in a special volume of Astérisque, in connection with the semester IHP of Fall 2004 "Méthodes explicites en théorie des nombres".

    • Book Chapter

  • Chapter 7: Hyperelliptic curves and the HCDLP, in Advances in Elliptic Curve Cryptography, 2005, CUP.
  • Chapter: Point counting, in Encyclopedia of Cryptography and Security (2nd edition), Springer Verlag, 2010, à paraître.

    • Referred conference proceedings

  • Speeding up the discrete log computation on curves with automorphisms, I. Duursma, P. Gaudry and F. Morain, Advances in Cryptology, Asiacrypt'99, Springer-Verlag, LNCS 1716, 103-121, 1999. © Springer-Verlag
  • An algorithm for solving the discrete log problem on hyperelliptic curves, P. Gaudry, Advances in Cryptology, Eurocrypt'2000, Springer-Verlag, LNCS 1807, 19-34, 2000. © Springer-Verlag. The title of the corresponding preprint was: A variant of the Adleman-DeMarrais-Huang algorithm and its application to small genera.
  • Counting points on hyperelliptic curves over finite fields, P. Gaudry and R. Harley. ANTS-IV, Springer-Verlag, LNCS 1838, 313-332, 2000. © Springer-Verlag
  • Finding secure curves with the Satoh-FGH algorithm and an early-abort strategy, M. Fouquet, P. Gaudry and R. Harley. Advances in Cryptology, Eurocrypt'2001, Springer-Verlag, LNCS 2045, 14-29, 2001. © Springer-Verlag.
  • On the invariants of the quotients of the Jacobian of a curve of genus 2, P. Gaudry et É. Schost. Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, Springer-Verlag, LNCS 2227, 373-386, 2001. © Springer-Verlag.
  • An extension of Kedlaya's algorithm to superelliptic curves, P. Gaudry and N. Gurel. Advances in Cryptology, Asiacrypt'2001, Springer-Verlag, LNCS 2248, 480-494, 2001. © Springer-Verlag.
  • A comparison and a combination of SST and AGM algorithms for counting points of elliptic curves in characteristic 2, P. Gaudry. Advances in Cryptology, Asiacrypt'2002, Springer-Verlag, LNCS 2501, 311-327, 2002. © Springer-Verlag.
  • Linear recurrences with polynomial coefficients and computation of the Cartier-Manin operator on hyperelliptic curves , A. Bostan, P. Gaudry and É. Schost. Proceedings of Fq7, Springer-Verlag LNCS 2948, 40--58, 2004, © Springer-Verlag.
  • Construction of secure random curves of genus 2 over prime fields , P. Gaudry and É. Schost. Advances in Cryptology, Eurocrypt 2004, Springer-Verlag, LNCS 3027, 239-256, 2004. © Springer-Verlag.
  • A low-memory parallel version of Matsuo, Chao and Tsujii's algorithm , P. Gaudry and É. Schost. Proceedings of ANTS 6, Springer-Verlag LNCS 3076, 208-222, 2004, © Springer-Verlag.
  • The Twist-AUgmented technique for key exchange, O. Chevassut, P.-A. Fouque, P. Gaudry and D. Pointcheval. PKC 2006, Springer-Verlag LNCS 3958, 410-426, 2006, © Springer-Verlag. (full version.)
  • Fast algorithms for computing the eigenvalue in the Schoof-Elkies-Atkin algorithm, P. Gaudry and F. Morain. Proceedings of ISSAC '06, ACM, 109-115, 2006.
  • The 2-adic CM method for genus 2 curves with application to cryptography, P. Gaudry, T. Houtmann, D. Kohel, C. Ritzenthaler and A. Weng. ASIACRYPT 2006, Springer-Verlag LNCS 4284, 114-129, 2006, © Springer-Verlag.
  • An L(1/3+ε) algorithm for the discrete logarithm problem for low degree curves, A. Enge and P. Gaudry. EUROCRYPT 2007, Springer-Verlag LNCS 4515, 379-393, 2007, © Springer-Verlag.
  • A GMP-based implementation of Schönhage-Strassen's large integer multiplication algorithm, P. Gaudry, A. Kruppa and P. Zimmermann. ISSAC 2007, ACM, 167-174.
  • The mpFq library and implementing curve-based key exchanges, P. Gaudry and E. Thomé. SPEED: Software Performance Enhancement for Encryption and Decryption, 49-64, 2007.
  • Faster multiplication in GF(2)[x], R. Brent, P. Gaudry, E. Thomé and P. Zimmermann. ANTS-VIII, Springer-Verlag LNCS 5011, 153-166, 2008, © Springer-Verlag.
  • Factorization of a 768-bit RSA modulus, T. Kleinjung, K. Aoki, J. Franke, A. Lenstra, E. Thomé, J. Bos, P. Gaudry, A. Kruppa, P. Montgomery, D. Osvik, H. te Riele, A. Timofeev and P. Zimmermann. Preprint, to appear in CRYPTO 2010.

    • Preprints

  • Some remarks on the elliptic curve discrete logarithm, P. Gaudry. Informal note, 7 pages. SLP.mag is a Magma code with the formulae of this note. example.mag illustrates its use.

    • Talks

  • Slides of the talk at Durham, June 28, 2000: "Counting points on genus 2 curves over finite fields".
  • Slides of the talk at ECC, October 4, 2000: "Hyperelliptic discrete logarithms".
  • Slides of the talk at ECC, October 31, 2001: "Algorithms for counting points on curves".
  • Slides of the talk at ECC, September 20, 2004: "Discrete logarithm in elliptic curves over extension fields of small degree".
  • Slides of the talk at the "Workshop on Cryptography and Related Mathematics", in Tokyo, August 2005: "Fast genus 2 arithmetic based on theta functions".
  • Slides of the talk at the workshop "Computational Challenges Arising in Algorithmic Number Theory and Cryptography", in Toronto, November 2006: "Variants of the Montgomery form based on Theta functions".
  • Slides of the talk at ECC, September 2007: "Genus 2 formulae based on Theta functions and RM Kummer surfaces".

    • Thesis

  • "Algorithmique des courbes hyperelliptiques et applications à la cryptologie", thèse de doctorat de l'École polytechnique, December 2000. Available in ps.gz or dvi.gz .
  • Algorithmique des courbes algébriques pour la cryptologie. Mémoire d'habilitation à diriger des recherches, UHP-Nancy 1, October 2008.