Counting points on elliptic curves over finite fields. (English) Zbl 0852.11073

Schoof, René

J. Théor. Nombres Bordx. 7, No. 1, 219-254 (1995).

The author reports on algorithms for counting the number of points on an elliptic curve over a finite field. The first one works well when the finite field is not too large and is based on Shank’s baby-step-giant-step strategy [D. Shanks, 1969 Number Theory Institute, Proc. Symp. Pure Math. 20, 415-440 (1971; Zbl 0223.12006)]. Then he discusses an improvement due to Mestre which avoids some group theoretical problems in this algorithm; this has been implemented in the computer algebra package PARI [H. Cohen, A course in computational number theory, Grad. Texts Math. 138 (1993; Zbl 0786.11071), Alg. 7.4.12; C. Batut, D. Bernardini, H. Cohen and M. Olivier, User’s guide to PARI-GP, version 1.30, Bordeaux (1990)]. The second algorithm is efficient when the endomorphism ring of the elliptic curve is known, and it is based on a reduction algorithm for lattices in \(\mathbb{R}^2\). A related algorithm due to Cornacchia and Lenstra’s proof of its correctness are also discussed. Finally the last algorithm is a deterministic one which runs in polynomial time and is based on calculations with torsion points. Practical improvements due to Atkin and Elkies are also presented. The latter methods can be extended to large finite fields of small characteristics, and its origin comes from cryptography [A. J. Menezes, S. A. Vanstone and R. J. Zuccherato, Math. Comput. 60, 407-420 (1993; Zbl 0809.14045)].

Reviewer: Amílcar Pacheco (Rio de Janeiro)

MSC:

11Y16	Number-theoretic algorithms; complexity
11G20	Curves over finite and local fields
14Q05	Computational aspects of algebraic curves
14H52	Elliptic curves

Keywords:

elliptic curve over a finite field; reduction algorithm for lattices; torsion points

Citations:

Zbl 0223.12006; Zbl 0786.11071; Zbl 0809.14045

Software:

ECPP; PARI/GP

References:

[1]	Atkin , A.O.L. : The Number of Points an an Elliptic Curve Modulo a Prime , manuscript, Chicago IL , January 1, 1988 .
[2]	Atkin , A.O.L. : Several public email messages , 1990 - 1992 .
[3]	Atkin , A.O.L. and Morain , F. : Elliptic curves and primality proving , Math. Comp. 61 ( 1993 ), 29 - 67 . MR 1199989 | Zbl 0792.11056 · Zbl 0792.11056
[4]	Batut , C. , Bernardi , D. , Cohen , H. and Olivier , M. : User’s Guide to PARI-GP, version 1.30 , Bordeaux February 1, 1990 .
[5]	Charlap , L.S. , Coley , R. and Robbins , D.P. : Enumeration of rational Points on Elliptic Curves over Finite Fields , manuscript, Princeton 1992 .
[6]	Cohen , H. : A course in computational number theory, Graduate Texts in Math. 138 , Springer-Verlag , Berlin Heidelberg New York 1993 . MR 1228206 | Zbl 0786.11071 · Zbl 0786.11071
[7]	Cornacchia , G. : Su di un metodo per la risoluzione in numeri interi dell’equazione \Sigma nh=0 Chxn-hyh = P . Giornale di Mat. di Battaglini 46 ( 1908 ), 33 - 90 . JFM 39.0258.02 · JFM 39.0258.02
[8]	Couveignes , J.-M. and Morain , F. : Schoof’s algorithm and isogeny cycles, Proceedings of the ANTS conference, Ithaca 1994 , Lecture Notes in Computer Science 1994 . Zbl 0849.14024 · Zbl 0849.14024
[9]	Couveignes , J.-M. : Computing isogenies in low characteristic , Thesis Bordeaux 1994 . To appear.
[10]	Elkies , N.D. : Explicit Isogenies , manuscript, Boston MA , 1992 .
[11]	Hartshorne , R. : Algebraic Geometry, Graduate Texts in Math. 52 , Springer-Verlag , Berlin Heidelberg New York 1977 . MR 463157 | Zbl 0367.14001 · Zbl 0367.14001
[12]	Lang , S. : Elliptic .Functions , Addison-Wesley , Reading MA 1973 . MR 409362 | Zbl 0316.14001 · Zbl 0316.14001
[13]	Lehmann , F. , Maurer , M. , Müller , V. and Shoup , V. : Counting the number of points on elliptic curves over finite fields of characteristic greater than three . Preprint 1994 . MR 1322712 · Zbl 0839.11026
[14]	Lenstra , H.W. : Elliptic curves and number-theoretical algorithms , Proc. of the International Congress of Math., Berkeley 1986 , 99 - 120 . MR 934218 | Zbl 0686.14039 · Zbl 0686.14039
[15]	Lenstra , H.W. : Letter to H. Cohen , August 16, 1990 .
[16]	Menezes , A.J. , Vanstone , S.A. and Zuccherato , R.J. : Counting points on elliptic curves over F2m, Math . Comp. 60 ( 1993 ), 407 - 420 , MR 1153167 | Zbl 0809.14045 · Zbl 0809.14045
[17]	Morain , F. : Calcul du nombre de points sur une courbe elliptique dans un corps fini: aspects algorithmiques , Proceedings of the Journées Arithmétiques, Bordeaux 1993 .
[18]	Schoof , R. : Elliptic curves over finite fields and the computation of square roots mod p , Math. Comp. 44 ( 1985 ), 483 - 494 . MR 777280 | Zbl 0579.14025 · Zbl 0579.14025
[19]	Shanks , D. : Class Number, a Theory of Factorization, and Genera, 1969 Number Theory Institute, Proc. of Symp. in Pure Math. 20 , AMS , Providence RI 1971 . MR 316385 | Zbl 0223.12006 · Zbl 0223.12006
[20]	Shanks , D. : Five number theoretical algorithms , Proc. 2nd Manitoba conference on numerical math., (Congressus Numerantium VII, Univ. Manitoba Winnipeg ), ( 1972 ), 51 - 70 . MR 371855 | Zbl 0307.10015 · Zbl 0307.10015
[21]	Silverman , J. : The Arithmetic of Elliptic Curves, Graduate Texts in Mathematics 106 , Springer-Verlag , Berlin Heidelberg New York 1986 . MR 817210 | Zbl 0585.14026 · Zbl 0585.14026