Satoh’s algorithm in characteristic 2. (English) Zbl 1027.11045

The author gives an algorithm for counting points on arbitrary ordinary elliptic curves over finite fields of characteristic 2, extending the \(O(\log^5q)\) method given by T. Satoh [J. Ramanujan Math. Soc. 15, 247-270 (2000; Zbl 1009.11051)], giving the asymptotically fastest point counting algorithm known to date.


11G20 Curves over finite and local fields
14G50 Applications to coding theory and cryptography of arithmetic geometry


Zbl 1009.11051
Full Text: DOI


[1] Henri Cohen, A course in computational algebraic number theory, Graduate Texts in Mathematics, vol. 138, Springer-Verlag, Berlin, 1993. · Zbl 0786.11071
[2] Andreas Enge, Elliptic curves and their applications to cryptography, Kluwer Academic Publishers, 1999. · Zbl 1335.11002
[3] Mireille Fouquet, Pierrick Gaudry and Robert Harley, An extension of Satoh’s algorithm and its implementation, J. Ramanujan Math. Soc. 15 (2000), no. 4, 281-318. CMP 2001:05 · Zbl 1009.11048
[4] Donald E. Knuth, The art of computer programming. Vol. 2, 2nd ed., Addison-Wesley Publishing Co., Reading, Mass., 1981. Seminumerical algorithms; Addison-Wesley Series in Computer Science and Information Processing. · Zbl 0477.65002
[5] Neal Koblitz, Elliptic curve cryptosystems, Math. Comp. 48 (1987), no. 177, 203 – 209. · Zbl 0622.94015
[6] Serge Lang, Elliptic functions, 2nd ed., Graduate Texts in Mathematics, vol. 112, Springer-Verlag, New York, 1987. With an appendix by J. Tate. · Zbl 0615.14018
[7] Victor S. Miller, Use of elliptic curves in cryptography, Advances in cryptology — CRYPTO ’85 (Santa Barbara, Calif., 1985) Lecture Notes in Comput. Sci., vol. 218, Springer, Berlin, 1986, pp. 417 – 426.
[8] Takakazu Satoh, The canonical lift of an ordinary elliptic curve over a finite field and its point counting, J. Ramanujan Math. Soc. 15 (2000), no. 4, 247 – 270. · Zbl 1009.11051
[9] René Schoof, Elliptic curves over finite fields and the computation of square roots mod \?, Math. Comp. 44 (1985), no. 170, 483 – 494. · Zbl 0579.14025
[10] Joseph H. Silverman, The arithmetic of elliptic curves, Graduate Texts in Mathematics, vol. 106, Springer-Verlag, New York, 1986. · Zbl 0585.14026
[11] Jacques Vélu, Isogénies entre courbes elliptiques, C. R. Acad. Sci. Paris Sér. A-B 273 (1971), A238 – A241 (French). · Zbl 0225.14014
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.