Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

 
 

 

Elliptic curves over finite fields and the computation of square roots mod $ p$


Author: René Schoof
Journal: Math. Comp. 44 (1985), 483-494
MSC: Primary 11Y16; Secondary 11G20, 14G15
DOI: https://doi.org/10.1090/S0025-5718-1985-0777280-6
MathSciNet review: 777280
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: In this paper we present a deterministic algorithm to compute the number of $ {{\mathbf{F}}_q}$-points of an elliptic curve that is defined over a finite field $ {{\mathbf{F}}_q}$ and which is given by a Weierstrass equation. The algorithm takes $ O({\log ^9}q)$ elementary operations. As an application we give an algorithm to compute square roots $ \bmod p$. For fixed $ x \in {\mathbf{Z}}$, it takes $ O({\log ^9}p)$ elementary operations to compute $ \sqrt x \bmod p$.


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

  • [1] I. Borosh, C. Moreno & H. Porta, "Elliptic curves over finite fields. I," Proc. 1972 Number Theory Conference (University of Colorado), Boulder, 1972, pp. 147-155. MR 0404263 (53:8066)
  • [2] I. Borosh, C. Moreno & H. Porta, "Elliptic curves over finite fields, II," Math. Comp., v. 29, 1975, pp. 951-964. MR 0404264 (53:8067)
  • [3] M. Deuring, "Die Typen der Multiplikatorenringe elliptischer Funktionenkörper," Abh. Math. Sem. Hamburg, v. 14, 1941, pp. 197-272. MR 0005125 (3:104f)
  • [4] D. Knuth, The Art of Computer Programming, vol. II (Seminumerical Algorithms), Addison-Wesley, Reading, Mass., 1981. MR 633878 (83i:68003)
  • [5] S. Lang, Elliptic Curves; Diophantine Analysis, Springer-Verlag, Berlin and New York, 1978. MR 518817 (81b:10009)
  • [6] S. Lang and H. Trotter, Frobenius Distributions in $ G{L_2}$-Extensions, Lecture Notes in Math., vol. 504, Springer-Verlag, Berlin and New York, 1976. MR 0568299 (58:27900)
  • [7] H. Petersson, "Über die Entwicklungskoeffizienten der automorphen Formen," Acta Math., v. 58, 1932, pp. 169-215. MR 1555346
  • [8] J. B. Rosser & L. Schoenfeld, "Approximate formulas for some functions of prime numbers," Illinois J. Math., v. 6, 1962, pp. 64-94. MR 0137689 (25:1139)
  • [9] J.-P. Serre & J. Tate, "Good reduction of abelian varieties," Ann. of Math., v. 88, 1968, pp. 492-517. MR 0236190 (38:4488)
  • [10] D. Shanks, Class Number, A Theory of Factorization and Genera, Proc. Sympos. Pure Math., vol. 20, Amer. Math. Soc., Providence, R. I., 1970, pp. 415-440. MR 0316385 (47:4932)
  • [11] D. Shanks, "Five number-theoretic algorithms," Congressus Numerantium No. VII; Proc. 2nd Manitoba Conf. on Numerical Math. (University of Manitoba), 1972, pp. 51-70. MR 0371855 (51:8072)
  • [12] J. Tate, "The arithmetic of elliptic curves," Invent. Math., v. 23, 1974, pp. 179-206. MR 0419359 (54:7380)

Similar Articles

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

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


Additional Information

DOI: https://doi.org/10.1090/S0025-5718-1985-0777280-6
Keywords: Elliptic curves, finite fields, factorization, polynomials, computational number theory
Article copyright: © Copyright 1985 American Mathematical Society

American Mathematical Society