Satoh’s algorithm in characteristic 2
HTML articles powered by AMS MathViewer
- by Berit Skjernaa PDF
- Math. Comp. 72 (2003), 477-487 Request permission
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
- Henri Cohen, A course in computational algebraic number theory, Graduate Texts in Mathematics, vol. 138, Springer-Verlag, Berlin, 1993. MR 1228206, DOI 10.1007/978-3-662-02945-9
- Andreas Enge, Elliptic curves and their applications to cryptography, Kluwer Academic Publishers, 1999.
- 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.
- Donald E. Knuth, The art of computer programming. Vol. 2, 2nd ed., Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley Publishing Co., Reading, Mass., 1981. Seminumerical algorithms. MR 633878
- Neal Koblitz, Elliptic curve cryptosystems, Math. Comp. 48 (1987), no. 177, 203–209. MR 866109, DOI 10.1090/S0025-5718-1987-0866109-5
- 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, DOI 10.1007/978-1-4612-4752-4
- 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, DOI 10.1007/3-540-39799-X_{3}1
- 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
- René Schoof, Elliptic curves over finite fields and the computation of square roots mod $p$, Math. Comp. 44 (1985), no. 170, 483–494. MR 777280, DOI 10.1090/S0025-5718-1985-0777280-6
- Joseph H. Silverman, The arithmetic of elliptic curves, Graduate Texts in Mathematics, vol. 106, Springer-Verlag, New York, 1986. MR 817210, DOI 10.1007/978-1-4757-1920-8
- Jacques Vélu, Isogénies entre courbes elliptiques, C. R. Acad. Sci. Paris Sér. A-B 273 (1971), A238–A241 (French). MR 294345
Additional Information
- Berit Skjernaa
- Affiliation: University of Aarhus, Department of Mathematics, Ny Munkegade, 8000 Aarhus C, Denmark
- Email: skjernaa@imf.au.dk
- 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
- © Copyright 2002 American Mathematical Society
- 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
- MathSciNet review: 1933832