Counting points on elliptic curves over finite fields
type: Item
instance of: scholarly article
title: Counting points on elliptic curves over finite fields
zbMATH Open document ID: 0852.11073
published in: Journal de Théorie des Nombres de Bordeaux
publication date: 1996-03-24T00:00:00Z
full work available at URL: http://www.numdam.org/item
full work available at URL: https://eudml.org/doc/93624
full work available at URL: jtnb7-1.html
review text: 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 [\textit{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 [\textit{H. Cohen}, A course in computational number theory, Grad. Texts Math. 138 (1993; Zbl 0786.11071), Alg. 7.4.12; \textit{C. Batut}, \textit{D. Bernardini}, \textit{H. Cohen} and \textit{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 [\textit{A. J. Menezes}, \textit{S. A. Vanstone} and \textit{R. J. Zuccherato}, Math. Comput. 60, 407-420 (1993; Zbl 0809.14045)].
Mathematics Subject Classification ID: 11Y16
Mathematics Subject Classification ID: 11G20
Mathematics Subject Classification ID: 14Q05
Mathematics Subject Classification ID: 14H52
zbMATH DE Number: 858026
zbMATH Keywords: elliptic curve over a finite field
zbMATH Keywords: reduction algorithm for lattices
zbMATH Keywords: torsion points
author: René Schoof
reviewed by: Amílcar Pacheco
describes a project that uses: PARI/GP
describes a project that uses: ECPP
MaRDI profile type: Publication
OpenAlex ID: W2037816851
cites work: Elliptic Curves and Primality Proving
cites work: Q3139838
cites work: Q4847913
cites work: Q4143433
cites work: Q4075566
cites work: Q4847916
cites work: Q4204265
cites work: Counting Points on Elliptic Curves Over F 2 m
cites work: Elliptic Curves Over Finite Fields and the Computation of Square Roots mod p
cites work: Q5628224
cites work: Q4063214
cites work: Q3710637
DOI: 10.5802/JTNB.142
description: scientific article; zbMATH DE number 858026