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$.

- 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 https://doi.org/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 https://doi.org/10.1007/BF02940746 - Donald E. Knuth,
*The art of computer programming. Vol. 2*, 2nd ed., Addison-Wesley Publishing Co., Reading, Mass., 1981. Seminumerical algorithms; Addison-Wesley Series in Computer Science and Information Processing. 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** - Serge Lang and Hale Trotter,
*Frobenius distributions in ${\rm GL}_{2}$-extensions*, Lecture Notes in Mathematics, Vol. 504, Springer-Verlag, Berlin-New York, 1976. Distribution of Frobenius automorphisms in ${\rm GL}_{2}$-extensions of the rational numbers. MR**0568299** - Hans Petersson,
*Über die Entwicklungskoeffizienten der automorphen Formen*, Acta Math.**58**(1932), no. 1, 169–215 (German). MR**1555346**, DOI https://doi.org/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 https://doi.org/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) Utilitas Math., Winnipeg, Man., 1973, pp. 51–70. Congressus Numerantium, No. VII. MR**0371855** - John T. Tate,
*The arithmetic of elliptic curves*, Invent. Math.**23**(1974), 179–206. MR**419359**, DOI https://doi.org/10.1007/BF01389745

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

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

Additional Information

Keywords:
Elliptic curves,
finite fields,
factorization,
polynomials,
computational number theory

Article copyright:
© Copyright 1985
American Mathematical Society