Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

 
 

 

Counting points on elliptic curves over $ \bold F\sb {2\sp m}$


Authors: Alfred J. Menezes, Scott A. Vanstone and Robert J. Zuccherato
Journal: Math. Comp. 60 (1993), 407-420
MSC: Primary 11Y16; Secondary 11G20, 11T71, 14H52
DOI: https://doi.org/10.1090/S0025-5718-1993-1153167-9
MathSciNet review: 1153167
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: In this paper we present an implementation of Schoof's algorithm for computing the number of $ {F_{{2^m}}}$-points of an elliptic curve that is defined over the finite field $ {F_{{2^m}}}$. We have implemented some heuristic improvements, and give running times for various problem instances.


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

  • [1] G. Agnew, R. Mullin, and S. Vanstone, An implementation of elliptic curve cryptosystems over $ {F_{{2^{155}}}}$, preprint. MR 1083769 (91j:94021)
  • [2] A. Atkin, The number of points on an elliptic curve modulo a prime, unpublished manuscript, 1991.
  • [3] J. Buchmann and V. Muller, Computing the number of points of elliptic curves over finite fields, presented at International Symposium on Symbolic and Algebraic Computation, Bonn, July 1991.
  • [4] L. Charlap, R. Coley, and D. Robbins, Enumeration of rational points on elliptic curves over finite fields, preprint.
  • [5] N. Koblitz, Elliptic curve cryptosystems, Math. Comp. 48 (1987), 203-209. MR 866109 (88b:94017)
  • [6] -, Constructing elliptic curve cryptosystems in characteristic 2, Advances in Cryptology-- Proc. Crypto '90, Lecture Notes in Comput. Sci., vol. 537, Springer-Verlag, Berlin, 1991, pp. 156-167. MR 1232869
  • [7] -, CM-curves with good cryptographic properties, Advances in Cryptology--Proc. Crypto '91, Lecture Notes in Comput. Sci., vol. 576, Springer-Verlag, Berlin, 1992, pp. 279-287. MR 1243654 (94e:11134)
  • [8] S. Lang, Elliptic curves: Diophantine analysis, Springer-Verlag, Berlin, 1978. MR 518817 (81b:10009)
  • [9] A. Menezes and S. Vanstone, Isomorphism classes of elliptic curves over finite fields of characteristic 2, Utilitas Math. 38 (1990), 135-153. MR 1093882 (92a:11071)
  • [10] V. Miller, Uses of elliptic curves in cryptography, Advances in Cryptology--Proc. Crypto '85, Lecture Notes in Comput. Sci., vol. 218, Springer-Verlag, Berlin, 1986, pp. 417-426. MR 851432 (88b:68040)
  • [11] R. Mullin, I. Onyszchuk, S. Vanstone, and R. Wilson, Optimal normal bases in $ GF({p^n})$, Discrete Appl. Math. 22 (1988/89), 149-161. MR 978054 (90c:11092)
  • [12] J. Pollard, Monte Carlo methods for index computation $ \pmod p$, Math. Comp. 32 (1978), 918-924. MR 0491431 (58:10684)
  • [13] R. Schoof, Elliptic curves over finite fields and the computation of square roots $ \bmod\, p$, Math. Comp. 44 (1985), 483-494. MR 777280 (86e:11122)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 11Y16, 11G20, 11T71, 14H52

Retrieve articles in all journals with MSC: 11Y16, 11G20, 11T71, 14H52


Additional Information

DOI: https://doi.org/10.1090/S0025-5718-1993-1153167-9
Article copyright: © Copyright 1993 American Mathematical Society

American Mathematical Society