[2016] [2015] [2014] [2013] [2012] [2011] [2010] [2009] [2008] [2007] [2006] [2005] [2004] [2003] [2002] [2001] [2000] [1999] [1998] [1997] [1996] [1994] [1993] [1991]

Note: the years below correspond to the first preprint, not to the final publication dates.


Computing the ρ constant, with Jérémie Detrey and Pierre-Jean Spaenlehauer, preprint, 3 pages, October 2016.

Factorisation of RSA-220 with CADO-NFS, with Shi Bai, Pierrick Gaudry, Alexander Kruppa and Emmanuel Thomé, 3 pages, May 2016. [HAL]. RSA-220 is part of the RSA Factoring Challenge.

Twelve New Primitive Binary Trinomials, with Richard P. Brent, preprint, 2 pages, 2016 [arxiv, HAL]


Imperfect Forward Secrecy: How Diffie-Hellman Fails in Practice, with David Adrian, Karthikeyan Bhargavan, Zakir Durumeric, Pierrick Gaudry, Matthew Green, J. Alex Halderman, Nadia Heninger, Drew Springall, Emmanuel Thomé, Luke Valenta, Benjamin VanderSloot, Eric Wustrow, Santiago Zanella-Beguelin, May 2015, to appear in the proceedings of CCS 2015. [HAL] [talk slides]. Best paper award.

Automatic Analysis, 5 pages. This is a preliminary version of a chapter for a book about collected works of Philippe Flajolet. I wrote that chapter in March to July 2012. While the book is not yet published, I make this text available here.

Magic Squares of Squares, with Paul Pierrat and François Thiriet, 2015.


Beyond Double Precision, research project submitted as Advanced Grant to the European Research Council, October 2014. This project was judged ``of high quality but not sufficient to pass to Step 2 of the evaluation''.

Better Polynomials for GNFS, with Shi Bai, Cyril Bouvier, and Alexander Kruppa, Mathematics of Computation, volume 85, pages 861-873, 2016 (preprint from September 2014). [HAL]

Note: the size-optimized RSA-1024 polynomial B1024 can be reproduced using CADO-NFS using the command sopt -n 135...563 -f rsa1024.poly1 -d 6 with that rsa1024.poly1 file.


Division-Free Binary-to-Decimal Conversion, with Cyril Bouvier, IEEE Transactions on Computers, volume 63, number 8, pages 1895-1901, August 2014. [HAL]

Discrete logarithm in GF(2809) with FFS, with Razvan Barbulescu, Cyril Bouvier, Jérémie Detrey, Pierrick Gaudry, Hamza Jeljeli, Emmanuel Thomé and Marion Videau, proceedings of PKC 2014, Lecture Notes in Computer Science Volume 8383, pages 221-238, 2014. [HAL]


Factorization of RSA-704 with CADO-NFS, with Shi Bai and Emmanuel Thomé, preprint, July 2012. [HAL]

Size Optimization of Sextic Polynomials in the Number Field Sieve, with Shi Bai, preprint, March 2012, revised June 2013. [HAL]

Avoiding adjustments in modular computations, preprint, March 2012.

Finding Optimal Formulae for Bilinear Maps, with Razvan Barbulescu, Jérémie Detrey and Nicolas Estibals, proceedings of WAIFI 2012, Bochum, Germany, July 16-19, LNCS 7369, pages 168-186, 2012.


Maximal Determinants and Saturated D-optimal Designs of Orders 19 and 37, with Richard P. Brent, William Orrick, and Judy-anne Osborn, 28 pages.

Numerical Approximation of the Masser-Gramain Constant to Four Decimal Digits: delta=1.819..., with Guillaume Melquiond and W. Georg Nowak, Mathematics of Computation, volume 82, number 282, pages 1235-1246, 2013. [HAL entry]

Ballot stuffing in a postal voting system, with Véronique Cortier, Jérémie Detrey, Pierrick Gaudry, Frédéric Sur, Emmanuel Thomé and Mathieu Turuani, proceedings of REVOTE 2011, International Workshop on Requirements Engineering for Electronic Voting Systems, Trento, Italy, August 29, 2011, pages 27-36.

Short Division of Long Integers, with David Harvey, proceedings of the 20th IEEE Symposium on Computer Arithmetic (ARITH 20), Tuebingen, July 25-27, 2011, pages 7-14. [HAL entry, DOI]

Note added July 27, 2011: the algorithm used by GMP 5 (implemented in the mpn_div_q function) was presented by Torbjörn Granlund in his invited talk at the ICMS 2006 conference.


Non-Linear Polynomial Selection for the Number Field Sieve [doi], with Thomas Prest, Journal of Symbolic Computation, special issue in the honour of Joachim von zur Gathen, volume 47, number 4, pages 401-409, 2012. [HAL]

Note added in June 2011: Namhun Koo, Gooc Hwa Jo and Soonhak Kwon extended our algorithm in this preprint.
Note added on September 30, 2011: Nicholas Coxon extended and analysed our algorithm in this preprint.

Calcul mathématique avec Sage [in french] with Alexandre Casamayou, Guillaume Connan, Thierry Dumont, Laurent Fousse, François Maltey, Matthias Meulien, Marc Mezzarobba, Clément Pernet and Nicolas M. Thiéry, 2010 [HAL].

Modern Computer Arithmetic, with Richard Brent, Cambridge University Press, 2010 [HAL entry].

Reliable Computing with GNU MPFR, proceedings of the 3rd International Congress on Mathematical Software (ICMS 2010), June 2010, pages 42-45, LNCS 6327, Springer. The original publication is (or will be) available on www.springerlink.com.

Why and how to use arbitrary precision, with Kaveh R. Ghazi, Vincent Lefèvre and Philippe Théveny, March 2010, Computing in Science and Engineering, volume 12, number 3, pages 62-65, 2010 (© IEEE).

An O(M(n) log n) algorithm for the Jacobi symbol, with Richard Brent, January 2010, Proceedings of the Ninth Algorithmic Number Theory Symposium (ANTS-IX), Nancy, France, July 19-23, 2010, LNCS 6197, pages 83-95, Springer Verlag [the original publication is or will be available at www.springerlink.com].

Factorization of a 768-bit RSA modulus, with Thorsten Kleinjung, Kazumaro Aoki, Jens Franke, Arjen K. Lenstra, Emmanuel Thomé, Joppe W. Bos, Pierrick Gaudry, Alexander Kruppa, Peter L. Montgomery, Dag Arne Osvik, Herman te Riele and Andrey Timofeev, Proceedings of Crypto'2010, Santa Barbara, USA, LNCS 6223, pages 333-350, 2010 [technical announcement].

The Great Trinomial Hunt, with Richard Brent, Notices of the American Mathematical Society, volume 58, number 2, pages 233-239, February 2011.


The glibc bug #10709, September 2009. [bugzilla entry]

Calcul formel : mode d'emploi. Exemples en Maple, with Philippe Dumas, Claude Gomez, Bruno Salvy, March 2009 (in french) [HAL entry].

Computing predecessor and successor in rounding to nearest, with Siegfried Rump, Sylvie Boldo and Guillaume Melquiond, BIT Numerical Mathematics, volume 49, number 2, pages 419-431, 2009.


Worst Cases for the Exponential Function in the IEEE 754r decimal64 Format, with Vincent Lefèvre and Damien Stehlé, LNCS volume 5045, pages 114-126, special LNCS issue following the Dagstuhl seminar 06021: Reliable Implementation of Real Number Algorithms: Theory and Practice, August 2008,

Ten New Primitive Binary Trinomials, with Richard Brent, Mathematics of Computation 78 (2009), pages 1197-1199 [Brent's web page].

Implementation of the reciprocal square root in MPFR, March 2008 (extended abstract), Dagstuhl Seminar Proceedings following Dagstuhl seminar 08021 (Numerical validation in current hardware architectures), January 06-11, 2008.

Landau's function for one million billions, with Marc Deléglise and Jean-Louis Nicolas, Journal de Théorie des Nombres de Bordeaux, volume 20, number 3, pages 625-671, 2008. A Maple program implementing the algorithm described in this paper is available from Jean-Louis Nicolas web page.

Faster Multiplication in GF(2)[x], with Richard P. Brent, Pierrick Gaudry and Emmanuel Thomé, Proceedings of the Eighth Algorithmic Number Theory Symposium (ANTS-VIII), May 17-22, 2008, Banff Centre, Banff, Alberta (Canada), A. J. van der Poorten and A. Stein, editors, pages 153--166, LNCS 5011, 2008. A preliminary version appeared as INRIA Research Report, November 2007.


A Multi-level Blocking Distinct Degree Factorization Algorithm, INRIA Research Report 6331, with Richard P. Brent, 16 pages, October 2007. This paper describes in detail the algorithm presented at the 8th International Conference on Finite Fields and Applications (Fq8), July 9-13, 2007, Melbourne, Australia [extended abstract], [Richard's slides]. A revised version appeared in a special issue of Contemporary Mathematics, volume 461, pages 47-58, 2008.

A GMP-based implementation of Schönhage-Strassen's large integer multiplication algorithm, with Pierrick Gaudry and Alexander Kruppa, Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC 2007), Waterloo, Ontario, Canada, pages 167-174, editor C.W.Brown, 2007.

Time- and Space-Efficient Evaluation of Some Hypergeometric Constants, with Howard Cheng, Guillaume Hanrot, Emmanuel Thomé and Eugene Zima, Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC 2007), Waterloo, Ontario, Canada, pages 85-91, editor C.W.Brown, 2007.

Worst Cases of a Periodic Function for Large Arguments, with Guillaume Hanrot, Vincent Lefèvre and Damien Stehlé, Proceedings of the 18th IEEE Symposium on Computer Arithmetic (ARITH'18), pages 133-140, Montpellier, France, 2007. A preliminary version appeared as INRIA Research Report 6106, January 2007.


Asymptotically Fast Division for GMP, October 2005, revised August 2006, October 2006 and February 2015.

Errors Bounds on Complex Floating-Point Multiplication, with Richard Brent and Colin Percival, Mathematics of Computation volume 76 (2007), pages 1469-1481. Some technical details are given in INRIA Research Report 6068, December 2006.

20 years of ECMSpringer-Verlag), with Bruce Dodson, Proceedings of ANTS VII, July 2006. A preliminary version appeared as INRIA Research Report 5834, February 2006.


MPFR: A Multiple-Precision Binary Floating-Point Library With Correct Rounding, with Laurent Fousse, Guillaume Hanrot, Vincent Lefèvre, Patrick Pélissier, INRIA Research Report RR-5753, November 2005. A revised version appeared in ACM TOMS (Transactions on Mathematical Software), volume 33, number 2, article 13, 2007.

Techniques algorithmiques et méthodes de programmation (in french), 11 pages, July 2005, appeared in Encyclopédie de l'informatique et des systèmes d'information, pages 929-935, Vuibert, 2006.

5,341,321, June 2005.

The Elliptic Curve Method, November 2002, revised April 2003 and September 2010, appeared in the Encylopedia of Cryptography and Security, Springer, 2005 (old link).

MPFR : vers un calcul flottant correct ? (in french), Interstices, 2005. A primitive trinomial of degree 6972593, with Richard Brent and Samuli Larvala, Mathematics of Computation, volume 74, number 250, pages 1001-1002, 2005.

An elementary digital plane recognition algorithm, with Yan Gerard and Isabelle Debled-Rennesson, appeared in Discrete Applied Mathematics, volume 151, issue 1-3, pages 169-183, 2005.

Searching Worst Cases of a One-Variable Function Using Lattice Reduction, with Damien Stehlé and Vincent Lefèvre, IEEE Transactions on Computers, volume 54, number 3, pages 340-346, 2005. A preliminary version appeared as INRIA Research Report 4586. Some results for the 2x function double-extended precision are available here. 2004:

Gal's Accurate Tables Method Revisited, with Damien Stehlé, INRIA Research Report RR-5359, October 2004. An improved version appeared in the Proceedings of Arith'17. Those ideas are demonstrated by an implementation of the exp2 function in double precision. Erratum in the final version of the paper: in Section 4, the simultaneous worst case for sin and cos is t0=1f09c0c6cde5e3 and not t0=31a93fddd45e3. See also my coauthor page.

Newton iteration revisited, with Guillaume Hanrot, March 2004. Arithmétique flottante, with Vincent Lefèvre, INRIA Research Report RR-5105, February 2004 (in french). A Formal Proof of Demmel and Hida's Accurate Summation Algorithm, with Laurent Fousse, January 2004. The Middle Product Algorithm, I. Speeding up the division and square root of power series, with Guillaume Hanrot and Michel Quercia, AAECC, volume 14, number 6, pages 415-438, 2004. A preliminary version appeared as INRIA Resarch Report 3973. Proposal for a Standardization of Mathematical Function Implementation in Floating-Point Arithmetic, with David Defour, Guillaume Hanrot, Vincent Lefèvre, Jean-Michel Muller and Nathalie Revol, January 2003, Numerical Algorithms, volume 37, number 1-4, pages 367-375, 2004. Extended version appeared as INRIA Research Report RR-5406. A long note on Mulders' short product, with Guillaume Hanrot, INRIA Research Report RR-4654, November 2002. A revised version appeared in the Journal of Symbolic Computation, volume 37, pages 391-401, 2004. A corrigendum appeared in 2014 (pdf). 2003:

Random number generators with period divisible by a Mersenne prime, with Richard Brent, Proceedings of Computational Science and its Applications (ICCSA), LNCS 2667, pages 1-10, 2003. [HAL]

A Binary Recursive Gcd Algorithm, with Damien Stehlé, INRIA Research Report RR-5050, December 2003. A revised version (© Springer-Verlag) is published in the Proceedings of the Algorithmic Number Theory Symposium (ANTS VI). [Erratum] [implementation in GMP]

Algorithms for finding almost irreducible and almost primitivive trinomials, with Richard Brent, April 2003, Proceedings of a Conference in Honour of Professor H. C. Williams, Banff, Canada (May 2003), The Fields Institute, Toronto. Accurate Summation: Towards a Simpler and Formal Proof, with Laurent Fousse, March 2003, in Proc. of RNC'5, pages 97-108. 102098959 [in french], décembre 2002, paru dans la Gazette du Cines, numéro 14, janvier 2003. A Fast Algorithm for Testing Reducibility of Trinomials mod 2 and Some New Primitive Trinomials of Degree 3021377, with Richard Brent and Samuli Larvala, Mathematics of Computation, volume 72, number 243, pages 1443-1452, 2003. A preliminary version appeared as Report PRG TR-13-00, Oxford University Computing Laboratory, December 2000. 2002:

Ten Consecutive Primes In Arithmetic Progression, with Harvey Dubner, Tony Forbes, Nik Lygeros, Michel Mizony and Harry Nelson, Mathematics of Computation, volume 71, number 239, pages 1323-1328, 2002.

Worst Cases and Lattice Reduction, with Damien Stehlé and Vincent Lefèvre, INRIA Research Report RR-4586, October 2002. Appeared in the proceedings of the 16th IEEE Symposium on Computer Arithmetic (Arith'16), IEEE Computer Society, pages 142-147, 2003.

A Proof of GMP Square Root, with Yves Bertot and Nicolas Magaud, Journal of Automated Reasoning, volume 29, 2002, pages 225--252, Special Issue on Automating and Mechanising Mathematics: In honour of N.G. de Bruijn. A preliminary version appeared as INRIA Research Report 4475. Aliquot Sequence 3630 Ends After Reaching 100 Digits, with M. Benito, W. Creyaufmüller and J. L. Varona, Experimental Mathematics, volume 11, number 2, pages 201-206. Note added 29 July 2008: in this paper, we say (page 203, middle of right column) "It is curious to note that the driver 29 * 3 * 11 * 31 has appeared in no place in any of the sequences given in Table 1"; Clifford Stern notes that this driver appears at index 215 of sequence 165744, which gives 29 * 3 * 7 * 11 * 312 * 37 * 10594304241173.


De l'algorithmique à l'arithmétique via le calcul formel, Habilitation à diriger des recherches, novembre 2001. (Transparents de la soutenance.)

Arithmétique en précision arbitraire, rapport de recherche INRIA 4272, septembre 2001, paru dans la revue "Réseaux et Systèmes Répartis, Calculateurs parallèles", volume 13, numéro 4-5, pages 357-386, 2001 [in french]. Tuning and Generalizing Van Hoeij's Algorithm, with Karim Belabas and Guillaume Hanrot, INRIA Research report 4124, February 2001. Efficient isolation of a polynomial real roots, with Fabrice Rouillier, INRIA Research report 4113, February 2001. Appeared in Journal of Computational and Applied Mathematics, volume 162, number 1, pages 33-50, 2004. Density results on floating-point invertible numbers, with Guillaume Hanrot, Joël Rivat and Gérald Tenenbaum, Theoretical Computer Science, volume 291, number 2, 2003, pages 135-141. (The slides of a related talk I gave in January 2002 at the workshop "Number Theory and Applications" in Luminy are here.) 2000:

Factorization of a 512-bit RSA Modulus, with Stefania Cavallar, Bruce Dodson, Arjen K. Lenstra, Walter Lioen, Peter L. Montgomery, Brian Murphy, Herman te Riele, Karen Aardal, Jeff Gilchrist, Gérard Guillerm, Paul Leyland, Joël Marchand, François Morain, Alec Muffett, Chris Putnam, Craig Putnam, Proceedings of Eurocrypt'2000, LNCS 1807, pages 1-18, 2000.

A proof of GMP fast division and square root implementations, September 2000. Speeding up the Division and Square Root of Power Series, with Guillaume Hanrot and Michel Quercia, INRIA Research Report 3973, July 2000. Factorization in Z[x]: the searching phase, with John Abbott and Victor Shoup, April 2000, Proceedings of ISSAC'2000 [HAL entry]. 1999:

Karatsuba Square Root, INRIA Research Report 3905, November 1999.

On Sums of Seven Cubes, with Francois Bertault and Olivier Ramaré, Mathematics of Computation, volume 68, number 227, pages 1303-1310, 1999.

Uniform Random Generation of Decomposable Structures Using Floating-Point Arithmetic with Alain Denise, Theoretical Computer Science, volume 218, number 2, 219--232, 1999. A preliminary version appeared as INRIA Research Report 3242, September 1997.


Estimations asymptotiques du nombre de chemins Nord-Est de pente fixée et de largeur bornée, avec Isabelle Dutour et Laurent Habsieger, INRIA Research Report RR-3585, décembre 1998 [in french].


Calcul formel : ce qu'il y a dans la boîte, journées X-UPS, octobre 1997.

Cinq algorithmes de calcul symbolique, INRIA Technical Report RT-0206, notes de cours d'un module de spécialisation du DEA d'informatique de l'Université Henri Poincaré Nancy 1, 1997 [in french].

Progress Report on Parallelism in MuPAD, with Christian Heckler and Torsten Metzner, Inria Research Report 3154, April 1997.


Polynomial Factorization Challenges, with L. Bernardin and M. Monagan, poster presented at the International Symposium on Symbolic and Algebraic Computation (ISSAC), July 1996, 4 pages.


GFUN: a Maple package for the manipulation of generating and holonomic functions in one variable, with Bruno Salvy, ACM Transactions on Mathematical Software, volume 20, number 2, 1994. A preliminary version appeared as INRIA Technical Report 143, October 1992.

Random walks, heat equation and distributed algorithms, with Guy Louchard, René Schott and Michael Tolley, Journal of Computational and Applied Mathematics, volume 53, pages 243-274, 1994. The n-Queens Problem, with Igor Rivin and Ilan Vardi, American Mathematical Monthly, volume 101, number 7, pages 629-639. 1993:

A Calculus of Random Generation, with Philippe Flajolet and Bernard Van Cutsem, Proceedings of European Symposium on Algorithms (ESA'93), LNCS 726, pages 169-180, 1993.

Epelle : un logiciel de détection de fautes d'orthographe, INRIA Research Report 2030, September 1993.


Automatic Average-case Analysis of Algorithms, with Ph. Flajolet and B. Salvy, Theoretical Computer Science, volume 79, number 1, pages 37-109, 1991.

Séries génératrices et analyse automatique d'algorithmes, PhD thesis (in french), École Polytechnique, Palaiseau, 1991 [in french]. Also available in postscript.