Point counting of an elliptic curve over GF(5569)

Takakazu Satoh
Department of Mathematics, Fac. Sci, Saitama University, Japan
Current Affiliation: Department of Mathematics, Tokyo Institute of Technology, Japan

Background: After the following research is completed, an asymptotically faster algorithm is developed (joint work with B. Skjernaa and Y. Taguchi). The new algorithm also works for p=2 and it seems to be faster and efficient for elliptic curve cryptography. For details, please read here. Assuming the Karatsuba multiplication, the time complexity of the following algorithm is O(N4.16) while that of the new algorithm is O(N3.66) with some precomputation.

The point counting algorithm for elliptic curves based on canonical lifting (T. Satoh: The canonical lift of an ordinary elliptic curve over a finite field and its point counting. J. Ramanujan Math. Soc. 15, 247-270 (2000)) is actually implemented and its running time is measured for finite fields of 5n elements. The result is as follows:
value of nfield size (in bit)min. timemax. time# of curves tested
30 69 128sec 135sec 12
69 160 1913sec 2071sec 12
130 301 14478sec 16899sec 12
217 503 75108sec 80285sec 6
435 1010 817860sec --- 1
569 1321 2236140sec --- 1

The program is written in C++ from scratch with cooperation of Prof. K. Araki at Tokyo Institute of Technology and his student Mr. K. Nakabayashi. No assembly code is involved to keep portability. (The multiprecision integer arithmetic package executes computation by 16bit -- this is a severe restriction of high level languages.) We used the Karatsuba method for multiplications. It is complied by g++2.95.1 with -O3 -mcpu=ultrasparc and tested on a 300MHz ultrasparc machine with 256MB RAM.

Remark: I hope this is the world record for characteristic five, simply because no one seemed to try large scale computations for characteristic five. For characteristic two, Frederik Vercauteren computed the number of points on an elliptic curve over GF(21999) by using Schoof-Elkies-Atkin based algorithm.

Note added on May, 11, 2000. Mireille Fouquet, Pierrick Gaudry, Robert Harley, announced the new record over GF(23001). They modified point counting algorithm by the canonical lift to the characteristic two case. However, according to thier web page, their preprint is "in preperation". It tunrned out that Berit Skjernaa independently succeeded such a modification. According to her preprint, she avoid some problems which seems to be inherent to the characteristic two, though her preprint does not mention large scale computation (at the moment writing this).

Note added on January 13, 2001. Above mentioned Foueqet, Gaudry and Harley's paper is published as

Mireille Fouquet, Pierrick Gaudry and Robert Harley: An extension of Satoh's algorithm and its implementation. J. Ramanujan Math. Soc. Vol. 15, No.4, 2000, pp.281-318.
The filed of their largest example (Oct. 5, 2000) is GF(28009).
I gave talks on theoretical background of above algorithm at:
Back to home page
Last update: 04/01/16 (YY/MM/DD)