Date:         Sat, 20 Jun 1998 09:16:12 -0400
Reply-To:     Reynald LERCIER <lercier@hol.fr>
Sender:       Number Theory List <NMBRTHRY@LISTSERV.NODAK.EDU>
From:         Reynald LERCIER <lercier@hol.fr>
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 (joux@celar.fr),
R. Lercier (lercier@hol.fr).

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.