Section: Scientific Foundations

Complex multiplication

Genus 1

Despite the achievements described above, random curves are sometimes difficult to use, since their cardinality is not easy to compute or some useful properties are too rare to occur (suitability for pairings, for instance). In some cases, curves with special properties can be used. For example, curves with complex multiplication (in brief CM), have easily-computable cardinalities. For example, the elliptic curve by the equation $y^2=x^3+x$ over $GF\left(p\right)$ has cardinality $p+1-2u$, when $p=u^2+v^2$, and computing this $u$ is easy.

The CM theory for genus 1 is well known, dating back to the middle of the nineteenth century (Kronecker, Weber, etc.). Its algorithmic aspects are also well understood; recently more work was done, largely by TANC . Twenty years ago, this theory was applied by Atkin to the primality proving of arbitrary integers, yielding the ECPP algorithm developed since then by F. Morain. Though the decision problem isPrime? was shown to be in P (by the work of Agrawal, Kayal, and Saxena in 2002), practical primality proving for large random numbers is still done only with ECPP.

These CM curves enabled A. Enge, R. Dupont and F. Morain to give an algorithm for building good curves for use in Identity Based Cryptosystems [41] .

CM curves are defined by algebraic integers, whose minimal polynomials have to be computed exactly, the coefficients being exact integers. The fastest algorithm to perform these computations requires a floating point evaluation of the roots of the polynomial to a high precision. F. Morain on one hand, and A. Enge (together with R. Schertz) on the other, have developed the use of new class invariants characterizing CM curves. The union of these two families is currently the state of the art in the field (see [8] ). More recently, F. Morain and A. Enge have designed a fast method for the computation of the roots of this polynomial over a finite field using Galois theory [44] . These invariants, together with this new algorithm, are incorporated in the working version of the program ECPP.

F. Morain analyzed a fast variant of ECPP, called fastECPP, which led him to gain one order of magnitude in the complexity of the problem (see [13] [63] ), reaching heuristically $O\left({(logN)}^{4+ϵ}\right)$ (compared to $O\left({(logN)}^{5+ϵ}\right)$ for the basic version). By comparison, the best proven version of Agrawal–Kayal–Saxena [59] has complexity $O\left({(logN)}^{6+ϵ}\right)$, and has not been implemented so far; the best randomized version [33] reaches the same $O\left({(logN)}^{4+ϵ}\right)$ bound but suffers from memory problems, and is not yet competitive. F. Morain implemented fastECPP, and was able to prove the primality of $10,000$ decimal digit numbers [13] , as opposed to $5,000$ for the basic (historical) version. Continual improvements to this algorithm led to new records in primality proving, some of which were obtained with his co-authors J. Franke, T. Kleinjung and T. Wirth [45] who developed their own programs. F. Morain set the current world record to 20,562 decimal digits in early June 2006 (compared to 15,071 two years earlier). This record was made possible by using an updated MPI-based implementation of the algorithm, and distributing the process on a cluster of 64-bit bi-processors (AMD Opteron(tm) Processor 250 at 2.39 GHz). In 2007, another large number was proven to be prime, namely $(2^{42737}+1)/3$ with $12,865$ decimal digits.

In his thesis, R. Dupont investigated the complexity of the evaluation of some modular functions and forms (such as the elliptic modular function $j$ and the Dedekind eta function). High precision evaluation of such functions is at the core of algorithms to compute class polynomials (used in complex multiplication) or modular polynomials (used in the SEA elliptic curve point counting algorithm).

Exploiting the deep connection between the arithmetic-geometric mean (AGM) and a special kind of modular forms known as theta constants, he devised an algorithm based on Newton iterations and the AGM that has quasi-optimal linear complexity. In order to certify the correctness of the result to a specified precision, a fine analysis of the algorithm and its complexity was necessary.

Using similar techniques, he has given a proven algorithm for the evaluation of the logarithm of complex numbers with quasi-optimal time complexity.

A. Enge has been able to analyse precisely the complexity of class polynomial computations via complex floating point approximations [5] . Using techniques from fast symbolic computation (multievaluation of polynomials) and results from R. Dupont's PhD thesis [40] , he has obtained two algorithms which are quasi-linear (up to logarithmic factors) in the output size. The second algorithm has been used for a record computation of a class polynomial of degree 100,000, the largest coefficient of which has almost 250,000 bits. The implementation is based on GMP , mpfr, mpc and mpfrcx (see Section 5); the only limiting factor for going further has become the memory requirements of the final result.

Alternative algorithms use $p$-adic approximations or the Chinese remainder theorem to compute class polynomials over the integers. A. Enge and his coauthors have presented an optimized algorithm based on Chinese remaindering in [2] and improved the number theoretic bounds underlying the complexity analysis. They have shown that all three different approaches have a quasi-linear complexity, while the the floating point algorithm appeared to be the fastest one in practice.

Inspired by [2] , A. Sutherland has come up with a new implementation of the Chinese remainder based algorithm that has led to new record computations [66] . Unlike the other algorithms, this approach does not need to hold the complete polynomial in main memory, but essentially only one coefficient at a time, which enables it to go much further. The main bottleneck is currently an extension of the algorithm to class invariants, which is work in progress by A. Enge.

Genus 2

The theory of Complex Multiplication also exists for non-elliptic curves, but is more intricate, and only recently can we dream to use them. Some of the recent results occurred as the work of R. Dupont (former member of TANC ) in his thesis.

R. Dupont has worked on adapting his algorithm to genus 2, which induces great theoretical and technical difficulties. He has studied a generalization of the AGM known as Borchardt sequences, proven the convergence of these sequences in a general setting, and determined the set of limits of such sequences in genus 2. In particular, he proved a theorem parametrizing the set of all possible limits of Borchardt sequences starting with a fixed 4-tuple. He developed an algorithm for the fast evaluation of theta constants in genus 2, and as a byproduct obtained an algorithm to compute the Riemann matrix of a given hyperelliptic curve: given the equation of such a curve, it computes a lattice $L$ such that the Jacobian of the curve is isomorphic to $ℂ/L$. These algorithms are both quasi-linear, and have been implemented (in C , using the multiprecision package GMP – see http://gmplib.org/ ).

Using these implementations, R. Dupont has began computing modular polynomials for groups of the form ${\Gamma }_0\left(p\right)$ in genus 2 (these polynomials link the genus 2 $j$-invariants of $p$-isogenous curves). He computed the modular polynomials for $p=2$, which had never been done before, and did some partial computations for $p=3$ (results are available at http://www.lix.polytechnique.fr/Labo/Regis.Dupont ).