The Canonical Lift of an Ordinary Elliptic Curve over a Finite Field and its Point Counting, by Takakazu Satoh

This paper has now appeared in the J. Ramanujan Math. Soc. Vol.15 No.4 (2000), pp.247-270, and so the preprint has been removed. This is a revision of number 184.

We develop a deterministic algorithm for the point counting of an elliptic curve E defined over the finite field with pN elements provided that p is small enough and that j(E) does not belong to the finite field with p2 elements. For simplicity, we are concerned to the case p>3. The so-called Schoof-Elkies-Atkin algorithm requires O((N log p)4 + \epsilon). Our algorithm is O(N3 + \epsilon) where O-constant depends (badly) on p. Our idea is totally different from SEA algorithm. We lift E to its canonical lift and compute the trace of Verschiebung (i.e. the dual of the Frobenius morphism) directly from characteristic zero information.

Summary of changes:

  1. All the remarks on concerning characteristic two in the previous version were deleted because Y2=X3+aX+b is always supersingular when characteristic of base field is two. In the revised version, Remark 2.9 sketches treatment for p=2.
  2. In the proof of Theorem 2.11(in the old version), it was not clear why the condition (iii) of Lemma 2.1 is satisfied. To give its proof, Lemma 2.7 is added and Theorem 2.8(of the revised version) is slightly modified.
  3. The proof of implication (iii) -> (i) of Theorem 2.3 is replaced and simplified.
  4. The implication (iv) -> (i) of Theorem 2.3 turned out to be true and its proof is included. This makes Lemma 2.5 and Theorem 2.6(in the old version) unnecessary.
  5. In Sect. 3, square root finding over a finite field is no longer necessary. Instead, we utilize the Hasse invariant. This makes our algorithm deterministic. Due to this reason, the final few lines of Prop. 3.3(in the old version) are deleted and some new lines are inserted at the end of proof of Theorem 3.3(in the revised version).
  6. In the revised version, the symbols $\xi$ and $\eta$ are exclusively used for coordinate functions. The $xi$ and $eta$ used for other purpose were changed to other symbols.
  7. Several typographical errors are fixed, including formulas giving $\alpha _i$ and $\beta _i$ in the proof of Proposition 3.2.


Takakazu Satoh <tsatoh@rimath.saitama-u.ac.jp>