Date:         Tue, 19 Sep 1995 17:30:27 EDT
Reply-To:     Francois Morain <>
Sender:       Number Theory List <NMBRTHRY@VM1.NODAK.EDU>
From:         Francois Morain <>
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

(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.