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
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:
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.
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.
The proof of implication (iii) -> (i) of Theorem 2.3
is replaced and simplified.
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.
In Sect. 3, square root finding over a finite field is no longer necessary.
Instead, we utilize the Hasse invariant.
This makes our algorithm
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).
In the revised version, the symbols $\xi$ and $\eta$ are exclusively used for
The $xi$ and $eta$ used for other purpose were changed to other symbols.
Several typographical errors are fixed, including
formulas giving $\alpha _i$ and $\beta _i$
in the proof of Proposition 3.2.
Takakazu Satoh <email@example.com>