Satoh's algorithm in characteristic 2

Author:
Berit Skjernaa

Journal:
Math. Comp. **72** (2003), 477-487

MSC (2000):
Primary 11G20, 11T71; Secondary 11G07, 14H52

DOI:
https://doi.org/10.1090/S0025-5718-02-01434-5

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 , extending the method given by Takakazu Satoh, giving the asymptotically fastest point counting algorithm known to date.

**[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*, 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**

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

Email:
skjernaa@imf.au.dk

DOI:
https://doi.org/10.1090/S0025-5718-02-01434-5

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