Sites Inria

Version française

CACAO Research team

Curves, Algebra, Computer Arithmetic, and so On

  • Leader : Guillaume Hanrot
  • Research center(s) : CRI Nancy - Grand Est
  • Field : Algorithmics, Programming, Software and Architecture
  • Theme : Algorithms, Certification, and Cryptography
  • Partner(s) : Université de Lorraine,CNRS
  • Collaborator(s) : CNRS, INRIA

Team presentation

The CACAO project-team has two concurring objectives:
  • Studying the arithmetic of curves of small genus, with in mind applications to cryptology,
  • Improving the efficiency and the reliability of arithmetics in a very broad sense (i.e., the arithmetics of a wide variety of objects).
These two objectives strongly interplay. Arithmetics are, of course, at the core of optimizing algorithms on curves, starting evidently with the arithmetic of curves themselves. On the other hand, curves can sometimes be a tool for some arithmetical problems like integer factorization. To reach these objectives, the project is structured along three axes: Curves, Arithmetics and Linear Algebra. The last one should be seen as an important tool for our main objectives, which is central enough so that we need to develop our own, dedicated algorithms and software to suit our needs.

Research themes

  • Algebraic curves: the main issue here is to investigate curves of small genus over finite fields (base field F_{p^n}, for various p and n), i.e., mainly: to compute in the Jacobian of a given curve, to be able to check that this variety is suitable for cryptography (largest prime dividing the cardinal) and to solve problems in those structures (discrete logarithm). Applications go from number theory (integer factorization) to cryptography (an alternative to RSA).
  • Arithmetics: we consider here algorithms working on multiple-precision integers, floating-points numbers, p-adic numbers and finite fields. For such basic data structures, we do not expect new algorithms with better asymptotic behavior to be discovered; however, since those are first-class objects in all our computations, every speedup is most welcome, even by a factor of 2 !
  • Solving large linear systems is a key point of factoring and discrete logarithm algorithms, which we need to investigate if curves are to be applied in cryptology. And lattices are central points of the new ideas that have emerged over the very last years for several problems in computer arithmetic or discrete logarithms algorithms. We thus consider here large sparse linear systems over a finite field, and often make use of lattice basis reduction algorithms for our application, though we do not study them per se.
The project team also maintains a important activity of software development. The corresponding software can be a testing ground, a result per se, a way to validate results, or all of those. An up-to-date list of software developed and distributed by the project-team is accessible.

International and industrial relations

  • Stockholm / GMP. Since 2000, our project-team made several contributions to the GNU MP (GMP for short) library developed by Torbjörn Granlund (Swox company, Stockholm, Sweden).
  • Canberra / Australian National University. Since 2000, we keep a strong collaboration with Richard Brent; in particular, a book describing the state of the art in multiple precision computer arithmetic (integers, integers modulo n, floating-point numbers) is being written.
  • Berlin (TU). We have a current project "Bilateral scientific co-operation programme" with Florian Hess' team at TU Berlin, for working on the study of some techniques to attack the discrete logarithm problem on elliptic curves.

Keywords: Algebraic curves Arithmetics Computer algebra