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.
*** SATOH-FGH ALGORITHM ***
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.
*** IMPLEMENTATION ***
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.
*** ANNOUNCEMENT ***
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
193940895056863504783294021995065119636064037744458121824706
256101375092227785899279859382375508813512228452707543448804
227830350453630318289993429955048544858271431235554925925218
016021462976522604806199992629607633615399045665748120403497
295724818612705811737001932873239713976031333307121192031140
124936716110261344299992343462618094707883381239575692354062
675177743128084928704789927053902757527426178584350294618098
340414692085330411964582201095084463986891949680756772569455
776175298098419627580620230881405697016837843911732490034219
592736044382123314677929838172853537747054427942739774461484
712209985999476777494287080574838937079674483708654377667748
782232512309071885437433718460626024619545730229857335859452
961591499827794731180323396776774693997980749628390806053785
208509477197767399825222359144733258976844620499589156331646
085956322156871493279308734719611148013330484292242206852555
894563150429003330357185835857959827198598539336567401817103
005203941979959470708629753376721197597388299770441615351946
293827847496574699722624775864568852009210270915236395433004
819982461492543540766219587259634877029770317456234950616362
600955
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:
Robert.Harley@polytechnique.orgFinally, a tiny demo of ECPC is now available for Linux PCs at the following URL:
http://www.xent.com/~harley/With best regards,