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 Free Access

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, vol. 138, Springer-Verlag, Berlin, 1993. MR**1228206****[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,*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. MR**633878****[Kob87]**Neal Koblitz,*Elliptic curve cryptosystems*, Math. Comp.**48**(1987), no. 177, 203–209. MR**866109**, 10.1090/S0025-5718-1987-0866109-5**[Lan87]**Serge Lang,*Elliptic functions*, 2nd ed., Graduate Texts in Mathematics, vol. 112, Springer-Verlag, New York, 1987. With an appendix by J. Tate. MR**890960****[Mil86]**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. MR**851432**, 10.1007/3-540-39799-X_31**[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**1801221****[Sch85]**René Schoof,*Elliptic curves over finite fields and the computation of square roots mod 𝑝*, Math. Comp.**44**(1985), no. 170, 483–494. MR**777280**, 10.1090/S0025-5718-1985-0777280-6**[Sil86]**Joseph H. Silverman,*The arithmetic of elliptic curves*, Graduate Texts in Mathematics, vol. 106, Springer-Verlag, New York, 1986. MR**817210****[V71]**Jacques Vélu,*Isogénies entre courbes elliptiques*, C. R. Acad. Sci. Paris Sér. A-B**273**(1971), A238–A241 (French). MR**0294345**

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:
http://dx.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