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

HTML articles powered by AMS MathViewer

- by René Schoof PDF
- Math. Comp.
**44**(1985), 483-494 Request permission

## 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

- I. Borosh, C. Moreno, and H. Porta,
*Elliptic curves over finite fields. I*, Proceedings of the 1972 Number Theory Conference (Univ. Colorado, Boulder, Colo.), Univ. Colorado, Boulder, Colo., 1972, pp. 147–155. MR**0404263** - I. Borosh, C. J. Moreno, and H. Porta,
*Elliptic curves over finite fields. II*, Math. Comput.**29**(1975), 951–964. MR**0404264**, DOI 10.1090/S0025-5718-1975-0404264-3 - Max Deuring,
*Die Typen der Multiplikatorenringe elliptischer Funktionenkörper*, Abh. Math. Sem. Hansischen Univ.**14**(1941), 197–272 (German). MR**5125**, DOI 10.1007/BF02940746 - 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** - Serge Lang,
*Elliptic curves: Diophantine analysis*, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 231, Springer-Verlag, Berlin-New York, 1978. MR**518817**, DOI 10.1007/978-3-662-07010-9 - Serge Lang and Hale Trotter,
*Frobenius distributions in $\textrm {GL}_{2}$-extensions*, Lecture Notes in Mathematics, Vol. 504, Springer-Verlag, Berlin-New York, 1976. Distribution of Frobenius automorphisms in $\textrm {GL}_{2}$-extensions of the rational numbers. MR**0568299**, DOI 10.1007/BFb0082087 - Hans Petersson,
*Über die Entwicklungskoeffizienten der automorphen Formen*, Acta Math.**58**(1932), no. 1, 169–215 (German). MR**1555346**, DOI 10.1007/BF02547776 - J. Barkley Rosser and Lowell Schoenfeld,
*Approximate formulas for some functions of prime numbers*, Illinois J. Math.**6**(1962), 64–94. MR**137689** - Jean-Pierre Serre and John Tate,
*Good reduction of abelian varieties*, Ann. of Math. (2)**88**(1968), 492–517. MR**236190**, DOI 10.2307/1970722 - Daniel Shanks,
*Class number, a theory of factorization, and genera*, 1969 Number Theory Institute (Proc. Sympos. Pure Math., Vol. XX, State Univ. New York, Stony Brook, N.Y., 1969) Amer. Math. Soc., Providence, R.I., 1971, pp. 415–440. MR**0316385** - Daniel Shanks,
*Five number-theoretic algorithms*, Proceedings of the Second Manitoba Conference on Numerical Mathematics (Univ. Manitoba, Winnipeg, Man., 1972) Congressus Numerantium, No. VII, Utilitas Math., Winnipeg, Man., 1973, pp. 51–70. MR**0371855** - John T. Tate,
*The arithmetic of elliptic curves*, Invent. Math.**23**(1974), 179–206. MR**419359**, DOI 10.1007/BF01389745

## Additional Information

- © Copyright 1985 American Mathematical Society
- 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