Satoh’s algorithm in characteristic 2

Skjernaa, Berit

doi:10.1090/S0025-5718-02-01434-5

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