Date:         Mon, 22 Apr 1996 09:16:35 EDT
Reply-To:     Francois Morain <morain@polytechnique.fr>
Sender:       Number Theory List <NMBRTHRY@VM1.NODAK.EDU>
From:         Francois Morain <morain@polytechnique.fr>
Subject:      #E_X(GF(2^1301))

We have established a new (as far as we know) record in elliptic curve
point counting over GF(2^n). This new record follows records we have
already done before, mainly, n = 701 (cf. [LM95]) and  n = 1009
(cf. [LM96]).
 
Let K = GF(2^1301)=GF(2)[T]/(T^1301+T^11+T^10+T+1) and put
 
a6 =  T^16+T^14+T^13+T^9+T^8+T^7+T^6+T^5+T^4+T^3.
 
Let E be the curve E: Y^2+XY=X^3+a6. Then #E(K)=2^1301+1-t where
 
t =
-12520204660458550994342381347414364580981597602551541937475251045091\
682467090516587665003925037001223752821603011654792837240825761437453\
092925430162137172566628268880767876046805121177132601520639
 
The method used is the Schoof-Elkies-Atkin algorithm incorporating
Lercier's algorithm [L96] for computing isogenies in small
characteristic.
 
The computation was done on several DEC alpha's. The time needed on a
single DEC alpha would have been 206 days among which 7 days were spent
computing isogenies. This is smaller than what we had for GF(2^1009)
(243 days for the whole computation, among which 155 days for computing
isogenies with the algorithm described in [C94]). All l up to 673 had to be
used.
 
Papers on this topic can be found in
 
                http://lix.polytechnique.fr/~morain/
 
and
 
                http://lix.polytechnique.fr/~lercier/
 
                R. Lercier and F. Morain
 
 
Bibliography
------------
 
[C94] Jean-Marc Couveignes, Quelques calculs en th\'eorie des
nombres, Universit\'e de Bordeaux I, 1994.
 
[LM95] R. Lercier and F. Morain, Counting the number of points of on
elliptic curves over finite fields: strategies and performances,
Proc. Eurocrypt '95, Lecture Notes in Computer Science 921, Springer,
1995, pp. 79-94.
 
[LM96] R. Lercier and F. Morain, Counting points on elliptic curves
over GF(p^n) using Couveigne's algorithm, Research Report
LIX/RR/95/09, Ecole Polytechnique-LIX, September 1995
 
[L96] R. Lercier, Computing isogenies in F(2^n),  H. Cohen(Ed.), Proc. ANTS II,
Lecture Notes in Computer Science, Springer-Verlag, to appear.