Date:         Wed, 21 Jan 2004 14:39:52 -0500
Reply-To:     Reynald LERCIER <lercier@CLUB-INTERNET.FR>
Sender:       Number Theory List <NMBRTHRY@LISTSERV.NODAK.EDU>
From:         Reynald LERCIER <lercier@CLUB-INTERNET.FR>
Subject:      Elliptic curves with complex multiplication

We would like to report that, with starting point the results published in [CoHe2002], we came to an efficient p-adic algorithm to compute elliptic curves with a given number of points.

It is well known that the heart of such a computation is most of the time the calculation of the Hilbert class polynomial H_D(X) for a discriminant D. The method of choice for this task used to rely on complex approximations of its roots, the j-invariants of elliptic curves with complex multiplication by an order in Q(sqrt(D)). The analysis of this method yields a complexity in time larger than O(|D|^(1+o(1))) (O(|D|^(3/2+o(1)) is for instance reported in [AgLaVe2003]) and a complexity in space equal to the size of the polynomial, that is O(|D|).

In the same spirit as the results published in the last years for counting points on algebraic curves of small genus, [CoHe2002] opens the way to p-adic methods for computing such polynomials. Under GRH, the complexity in time of these new algorithms is O(|D|^(1+o(1))).

A first approach to make use of these ideas is the so-called ``ordinary case'' which is currently investigated by Broker and Stevenhagen [BrSt2003]. Very briefly, they carefully choose, on input N, a discriminant D of size at most sqrt(N) and a prime p of size |D|, find by trial and error the j-invariant of a curve mod p having complex multiplication by the order of discriminant D. They lift it over the p-adics to obtain a curve in characteristic zero whose reduction modulo a suitable prime q close to N has exactly N rational points. By way of example, [BrSt2003] constructs a curve with exactly 10^30 points. The size of the associated D and p is about 10^8, and their 28-megabyte class polynomial (which is computed for the classical Weber function, a slightly smaller function than j) has degree 15610.

On our side, we developed the ``supersingular case'' [RiDe2004]. Even if the situation from a theoretical viewpoint is more intricate since here, the curves with complex multiplications reduce modulo p to supersingular curves, it enables however the use of a p-adic arithmetic for very small p. Especially for p = 2 which occurs in many cases, we obtained an algorithm with the same complexity, but much more efficient in practice. The use of other modular functions (in the spirit of work by Gee-Stevenhagen and Broker-Stevenhagen) is most likely compatible with our method although the best way to organize it is not yet completely clear to us.

We implemented it for discriminants D of increasing size which are known to be ``hard'' cases, mainly discriminants such that H_D has got a large prime degree h (that is close to sqrt(|D|)). We give below timings in seconds on a DEC alpha 731 MHz Alpha EV6 CPU. Non critical parts of this implementation are done in magma codes [MAGMA], other parts are written in C. Arithmetic operations are performed with the ZEN library [ZEN] built over the GMP library [GMP].

-D | h | 2-adic | Lift | H_D from | Total | | | precision | of js | js | | --------------------------------------------------------------- 10^3+19 | 13 | 211 | 0 s | 0 s | 0 s | 10^4+211 | 43 | 1151 | 0 s | 0 s | 0 s | 10^5+19 | 193 | 5718 | 1/2 s | 1/2 s | 1 s | 10^6+1219 | 443 | 19235 | 6 s | 6 s | 12 s | 10^7+3859 | 1151 | 74931 | 1 mn 45 | 1 mn 45 | 3 mn 30 | 10^8+2011 | 3617 | 261212 | 32 mn | 31 mn | 1 h 3 | 10^9+4099 | 21313 | 1450000 | 1 d 6 h | 6 d | 1 week | ----------------------------------------------------------------

The last entry, i.e D = -1000004099, is a huge computation. The result is a 4-gigabyte irreducible polynomial and we suspect that this is the current record. Also, because of the limited amount of memory available on the computer, we could not take benefit of a full FFT integer multiplication, that's why computing H_D from its roots took much more time than lifting the j-invariants.

R. Lercier ( E. Riboulet-Deyris (

[AgLaVe2003] A. Agashe, K. Lauter and R. Venkatesan, ``Constructing elliptic curves with a known number of points over a prime field''. High primes and Misdemeanous. Lectures in honor of the 60-th birthday of Hugh Cowie Williams, Fields Institute Communications Series, 2003. Available at

[BrSt2003] R. Br\"oker and P. Stevenhagen, ``Elliptic curves with a given number of points'', preprint, 2004. Available at

[CoHe2002] J.-M. Couveignes and T. Henocq, ``Action of modular correspondences around CM points'', Algorithmic Number Theory, 5th International Symposium, ANTS-V, Lecture Notes in Computer Science, pages 234--243, Springer, 2002.



[RiDe2004] E. Riboulet-Deyris, these de doctorat, in preparation.


PS: Checking details --------------------

We heuristically check the computation, by using the following properties of the Hilbert class polynomial: _ The constant coefficient of H_D is the cube of smooth integer. _ Modulo arbitrary primes which can be written as a norm in Q(sqrt(D)), H_D completely splits.

For instance, for D = -1000004099, the constant coefficient of H_D is a 1708853-bit integer, its smallest prime factor is 2 (raised to the 340998-th power) and its largest prime factor is 187499561.

Moreover, we have computed the factorization of H_D modulo two 50-digit primes,

p1 = 100000000000000000000004450000000000000000250050531, p2 = 100000000000000000000010330000000000000000250267797.

Factorizing H_D modulo p1 yields 21313 j-invariants which correspond to elliptic curves whose cardinality is known by advance, thanks to the complex multiplication theory, to be equal to

p1 + 1 +/- 20000000000000000000000445.

The smallest and the largest such j-invariants are




Modulo p2, we obtain 21313 j-invariants too. The corresponding elliptic curves have cardinalities equal to

p2 + 1 +/- 20000000000000000000001033.

Again, the smallest and the largest such j-invariants are