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

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 -points of an elliptic curve that is defined over a finite field and which is given by a Weierstrass equation. The algorithm takes elementary operations. As an application we give an algorithm to compute square roots . For fixed , it takes elementary operations to compute .

**[1]**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****[2]**I. Borosh, C. J. Moreno, and H. Porta,*Elliptic curves over finite fields. II*, Math. Comput.**29**(1975), 951–964. MR**0404264**, https://doi.org/10.1090/S0025-5718-1975-0404264-3**[3]**Max Deuring,*Die Typen der Multiplikatorenringe elliptischer Funktionenkörper*, Abh. Math. Sem. Hansischen Univ.**14**(1941), 197–272 (German). MR**5125**, https://doi.org/10.1007/BF02940746**[4]**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****[5]**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****[6]**Serge Lang and Hale Trotter,*Frobenius distributions in 𝐺𝐿₂-extensions*, Lecture Notes in Mathematics, Vol. 504, Springer-Verlag, Berlin-New York, 1976. Distribution of Frobenius automorphisms in 𝐺𝐿₂-extensions of the rational numbers. MR**0568299****[7]**Hans Petersson,*Über die Entwicklungskoeffizienten der automorphen Formen*, Acta Math.**58**(1932), no. 1, 169–215 (German). MR**1555346**, https://doi.org/10.1007/BF02547776**[8]**J. Barkley Rosser and Lowell Schoenfeld,*Approximate formulas for some functions of prime numbers*, Illinois J. Math.**6**(1962), 64–94. MR**0137689****[9]**Jean-Pierre Serre and John Tate,*Good reduction of abelian varieties*, Ann. of Math. (2)**88**(1968), 492–517. MR**236190**, https://doi.org/10.2307/1970722**[10]**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****[11]**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****[12]**John T. Tate,*The arithmetic of elliptic curves*, Invent. Math.**23**(1974), 179–206. MR**419359**, 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

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