Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Satoh's algorithm in characteristic 2

Author: Berit Skjernaa
Journal: Math. Comp. 72 (2003), 477-487
MSC (2000): Primary 11G20, 11T71; Secondary 11G07, 14H52
Published electronically: March 22, 2002
MathSciNet review: 1933832
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We give an algorithm for counting points on arbitrary ordinary elliptic curves over finite fields of characteristic $2$, extending the $O(\log^5q)$method given by Takakazu Satoh, giving the asymptotically fastest point counting algorithm known to date.

References [Enhancements On Off] (What's this?)

  • [Coh93] Henri Cohen, A course in computational algebraic number theory, Graduate Texts in Mathematics, Springer-Verlag, Berlin, 1993. MR 94i:11105
  • [Eng99] Andreas Enge, Elliptic curves and their applications to cryptography, Kluwer Academic Publishers, 1999.
  • [GH00] 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
  • [Knu98] Donald E. Knuth, Seminumerical algorithms, 3 ed., The art of computer programming, vol. 2, Addison-Wesley, 1998. MR 83i:68003 (2nd ed.)
  • [Kob87] Neal Koblitz, Elliptic curve cryptosystems, Math. Comp. 48 (1987), 203-209. MR 88b:94017
  • [Lan87] Serge Lang, Elliptic functions, 2nd ed., Graduate Texts in Mathematics, Springer-Verlag, New York, 1987. MR 88c:11028
  • [Mil86] Victor Miller, Use of elliptic curves in cryptography, Advances in Cryptology--CRYPTO'85, Lecture Notes in Computer Science 218 (1986), 417-426. MR 88b:68040
  • [Sat00] 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. MR 2001j:11049
  • [Sch85] René Schoof, Elliptic curves over finite fields and the computation of square roots mod $p$, Math. Comp. 44 (1985), 483-494. MR 86e:11122
  • [Sil86] Joseph H. Silverman, The arithmetic of elliptic curves, Graduate Texts in Mathematics, Springer-Verlag, New York, 1986. MR 87g:11070
  • [V71] Jacques Vélu, Isogénies entre courbes elliptiques, C.R. Acad. Sc. Paris 273 (1971), 238-241. MR 45:3414

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 11G20, 11T71, 11G07, 14H52

Retrieve articles in all journals with MSC (2000): 11G20, 11T71, 11G07, 14H52

Additional Information

Berit Skjernaa
Affiliation: University of Aarhus, Department of Mathematics, Ny Munkegade, 8000 Aarhus C, Denmark

Keywords: Satoh's algorithm, elliptic curves, finite fields, order counting
Received by editor(s): September 4, 2000
Received by editor(s) in revised form: March 15, 2001
Published electronically: March 22, 2002
Additional Notes: Research supported in part by a Ph.D. grant from CRYPTOMAThIC
Article copyright: © Copyright 2002 American Mathematical Society

American Mathematical Society