# 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.