Date:         Tue, 19 Sep 1995 17:30:27 EDT
Reply-To:     Francois Morain <morain@polytechnique.fr>
Sender:       Number Theory List <NMBRTHRY@VM1.NODAK.EDU>
From:         Francois Morain <morain@polytechnique.fr>
Subject:      #E(GF(2^1009))

As was announced last week during Atkin's conference in Chicago, we
have established a new (as far as we know) record in elliptic curve
point counting over GF(2^n). This new record was done for this special
occasion, so that there is no new result compared to our preceding record
(n = 701, as explained in [LM95]).
 
Let K = GF(2^1009)=GF(2)[T]/(T^1009+T^11+T^4+T^2+1) and put
 
a6 =  T^16+T^14+T^13+T^9+T^8+T^7+T^6+T^5+T^4+T^3,
 
and let E be the curve
 
E: Y^2+XY=X^3+a6
 
Then #E(K)=2^1009+1-t where
 
t = 550079058499 \
    3461414462440950171237941919763462052453456763226048365537759705821387 \
    6976282320229650340954505941334049799934180550652777226376997856386305.
 
The computation was done on several DEC alpha's. The time needed on a
single DEC alpha would have been 243 days, All primes l <= 509 had to be
used.
 
The method used is the Schoof-Elkies-Atkin algorithm incorporating
Couveignes's algorithm [C94] for computing isogenies in small
characteristic. The most recent version of our paper relating our work
can be found in
 
                http://lix.polytechnique.fr/~morain/
 
(see the preprint section). More papers on this topic are to be found
there too.
 
 
                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.