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