Date:         Sat, 20 Jun 1998 09:16:12 -0400
Reply-To:     Reynald LERCIER <>
Sender:       Number Theory List <NMBRTHRY@LISTSERV.NODAK.EDU>
From:         Reynald LERCIER <>
Subject:      Counting points of elliptic curves defined over GF(2^n).

CELAR, Rennes (France), Friday June 19 1998.

We achieved a new record (as far as we know) in elliptic curve point counting over GF(2^n): n = 1663. The previous record was n = 1301 [LM98].

Precisely, let

K = GF(2^1663) = GF(2)[t]/(t^1663+t^9+t^8+t^6+t^4+t^3+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^1663+1-c where

c = -3805068377240724240560419948872646673663242814390586530165014569\ 62916781408677934096482497519457837637874855654232311763302675255\ 23746599175801006570912836055290240895389634433448280940885630125\ 648226190181753105401361328308884068025195620144202704383.

The huge part of this computation was done by the second author at Ecole Polytechnique on a network of workstations (most of them are DEC alphas computers) at the end of his thesis. The last phase was recently finished at CELAR thanks to the first author on PII 300 MHz based PCs.

The method used is the classical Schoof-Elkies-Atkin algorithm [L97] incorporating second author's algorithm [L96] for computing isogenies in small characteristic and, last but not least, incorporating a completely new algorithm to obtain, at the end of SEA algorithm, c from partial informations modulo small coprime integers. This algorithm we called ``Chinese And Match'' (we plan to describe it later in a paper) has characteristics which are much better than the classical ``Match and Sort'' algorithm. It still has an asymptotical complexity in O(N^(1/2)log(N)) where N is the number of possibilities for c, but: 1) it works much faster than the classical Match and sort algorithm, 2) the space needed by the ``Chinese And Match'' algorithm is quite attractive because it should nearly be O(N^(1/4)log(N)) (instead of O(N^(1/2) for the Match and Sort algorithm), 3) it is straightforward to distribute it over a network of workstations.

The time needed on a single DEC alpha 266 MHz would have been approximately 330 days for the whole computation, among which, 29 days to compute isogenies.

The time needed for the ``Chinese And Match'' algorithm to find c among 6.5 10^14 possibilities was bounded by 3.5 days (worst case) for the ``Chinese And Match'' on a PII 300 MHz based PC and the computation was done in a single night (real time) on a network of 4 PC (using only 12 Mb memory).

A. Joux (, R. Lercier (

References ----------

[LM98] R. Lercier and F. Morain, Algorithms for computing isogenies between elliptic curves, Computational Perspectives on Number Theory, Proceedings of a Conference in Honor of A.O.L. Atkin, AMS/IP Studies in Advanced Mathematics, Volume 7, pp. 77-96, 1998.

[L97] R. Lercier, Algorithmique des courbes elliptiques dans les corps finis, These, June 1997.

[L96] R. Lercier, Computimg isogenies in GF(2^n), H. Cohen(Ed.), ANTS II, Lecture Notes in Computer Science, Springer-Verlag, Volume 1122, pp. 197-212, May 1996.