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 (reynald.lercier@m4x.org)
E. Riboulet-Deyris (riboulet@univ-tlse2.fr)
[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 http://arxiv.org/abs/math.NT/0111159.
[BrSt2003] R. Br\"oker and P. Stevenhagen, ``Elliptic curves with a
given number of points'', preprint, 2004. Available at
http://www.math.leidenuniv.nl/reports/2003.html.
[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.
[GMP] http://www.swox.com/gmp/
[MAGMA] http://magma.math.usyd.edu.au/
[RiDe2004] E. Riboulet-Deyris, these de doctorat, in preparation.
[ZEN] http://www.di.ens.fr/~zen/
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
260072138597316940423487181276341379878279278,
...
99998168925631215250832090446915489942654116900291.
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
1434778888446940502286948329326475989744342524,
...
99996090091764332527748041664578982519514204127070.