Elliptic Curve Point Counting reaches 8009 bits.

Fellow number-theorists,

It is a pleasure to announce the culmination of our Elliptic Curve Point Counting project. As you may recall, we extended the results reported by Professor Satoh in his preprint [Sat] to apply in characteristic two (and three) as described in [FGH].

We include a brief description of the resulting algorithm (referred to as Satoh-FGH to distinguish it from a different extension designed by Berit Skjernaa) for those interested. Others can skip over the next section.


The input to the algorithm is an elliptic curve E: y^2+x*y = x^3+a6 defined over a finite field F_q where q = 2^d.

First of all it is necessary to lift the curve E up to a curve defined over a certain 2-adic ring Z_q above F_q. Intuitively, Z_q is to F_q as the 2-adic integers Z_2 are to the 2-element field F_2. More precisely, Z_q is the unique (unramified) discrete valuation ring having residue field F_q.

By a result of Lubin-Serre-Tate, there is a canonical way to lift E by lifting its j-invariant from F_q to Z_q using the modular polynomial Phi_2. A direct implementation of LST would be slow due to computations of the (rather complicated) Frobenius in Z_q.

The extraordinary efficiency of the algorithm comes from a surprising insight due to Pr. Satoh: rather than lifting j up to J in isolation, it is faster to lift j along with all its conjugates j_i simultaneously. Indeed writing out the equations Phi_2(J_i, J_{i+1}) for 0 <= i < d yields an algebraic system over Z_q without Frobenius, which can be solved quickly by a multi-variate Newton iteration.

The first stage of Satoh-FGH is thus to compute all the J_i's to 2-adic precision O(2^n) where n = ceiling(d/2)+1.

Next for each i we find a curve y^2+x*y = x^3+A6 defined over Z_q and having j-invariant J_i. This is done with an ordinary Newton iteration to compute A6 to precision O(2^n).

Next for each curve, we find (half of) the X-coordinate of the non-trivial point in the kernel of the dual isogeny of the Frobenius. This is done with another Newton iteration to precision O(2^(n-1)).

Now, the trace of Frobenius can be written as a norm from Z_q to Z_2 of a certain partial trace. Each triple (J_i, A6, X) allows us to compute the square of one of the conjugate partial traces, using the formulae of Vélu, to precision O(2^(n+2)).

To finish, we compute the product of these conjugates and take a 2-adic square root, yielding the trace c of Frobenius to precision O(2^(n+1)), except for its sign.

As is well known, c is confined to the interval -2^(d/2+1),...,2^(d/2+1). Since it is necessarily equal to 1 modulo 4, the number of points q+1-c can be determined exactly.

Much more detail may of course be found in the referenced papers.


The algorithm just described requires O(d^3) memory space and in practice this is quite a lot for d as large as several thousand. Furthermore it is completely deterministic and the run-time is O(d^5) with naïve arithmetic methods and O(d^3.log d.log log d) with the best known algorithms.

Several implementations of Satoh-FGH have been written by yours truly. We dubbed them "ECPC", for Elliptic Curve Point Counting (made easy!) Great care was taken to reduce memory usage as much as possible so that it would not prevent us from carrying out large computations.

In our first announcement, on 10th of May, we gave the number of points on an essentially random curve with d = 3001. The result was obtained with ECPC using Karatsuba's algorithm for multiplication and Newton iterations for division, root-finding and so on.

Our second annoucement, on 28th of August, reported the number of points on a curve with d = 5003. The result was computed with an improved ECPC in which multiplication was done using evaluation and interpolation at 3 or 4 rational points, in the style of Toom's algorithm. This led to an overall speed-up by a factor of roughly three.

The current ECPC does multiplication using Fast Fourier Transforms modulo Fermat numbers, in the style of Schönhage's algorithm. This gives a further speed-up by a factor of 4.2 at the highest precisions used, and roughly two or three overall.

This software now reaches the best asymptotic speed possible with current mathematical knowledge. In addition, due to careful implementation, the constant factors in speed and memory usage are very low indeed.


As a result of this extensive theoretical and practical work, we are now able to announce the number of points on a curve defined over F_q with q = 2^8009.

It was obtained after nearly two weeks of computation on the fastest computer available to us, a 750 MHz Alpha UP2000 at Cornell Computer Systems Laboratory. Three SCSI hard discs were installed to extend the virtual memory space beyond the 16.9 Gigabytes necessary for the computation.

Let the field F_q be represented as F_2[t]/(f(t)) where f(t) is the irreducible polynomial t^8009 + t^3159 + 1. Let E be the curve:

y^2 + x y = x^3 + a6

where the coefficient a6 is 0x3F636F6420707520732774616857, encoded in hexadecimal by reducing modulo f(t) and setting t to 2. It comes from the ASCII encoding of Bugs Bunny's phrase, "What's up doc?".

The result we obtained after 1126400 seconds of CPU time is q+1-c where:

c = -173781496855947505026635002869635953808229335381570056464621

We are very grateful to the following people who provided the computing resources needed to establish this and our other recent records:

Paul Bourke (Swinburne Astrophysics & Supercomputing) Rajit Manohar (Cornell Computer Systems Laboratory) Tom Morris (Alpha Processor Inc)

For reference we also mention ECPC's run-times at smaller sizes such as 1000, 2000 or 4000 bits: they are currently 22 minutes, 3 hours 2 minutes or 29 hours 19 minutes respectively.

As a service to the mathematical community, we would be pleased to run ECPC on curves (in characteristic two) of interest to colleagues on the NMBRTHRY list. Please send any queries to:


Finally, a tiny demo of ECPC is now available for Linux PCs at the following URL:


With best regards,

Robert Harley
Pierrick Gaudry, Mireille Fouquet, François Morain
(École polytechnique)
Mireille Fouquet, Pierrick Gaudry, Robert Harley,
"On Satoh's algorithm and its implementation",
Research report LIX/RR/00/06,
Laboratoire d'informatique de l'École polytechnique.
Takakazu Satoh,
"The Canonical Lift of an Ordinary Elliptic Curve over a Finite Field
and its Point Counting",
Preprint, 1999.