Schoof’s algorithm and isogeny cycles. (English) Zbl 0849.14024

Couveignes, Jean-Marc; Morain, François

Adleman, Leonard M. (ed.) et al., Algorithmic number theory. 1st international symposium, ANTS-I, Ithaca, NY, USA, May 6-9, 1994. Proceedings. Berlin: Springer-Verlag. Lect. Notes Comput. Sci. 877, 43-58 (1994).

Let \(E\) be an elliptic curve over a finite field \(\mathbb{F}_p\) where \(p\) is a large prime number. Schoof’s algorithm computes the number \(N\) of \(\mathbb{F}_p\)-rational points on \(E\) by calculating \(N\) modulo \(l\) for sufficiently many small prime numbers \(l\). The calculation of \(N\) modulo \(l\) uses the connection of \(N\) with the Frobenius endomorphism \(\pi_E\) acting on the \(l\)-adic Tate module of \(E\). The improvement of Atkin and Elkies makes use of those prime numbers \(l\) (called “good primes”), where the eigenvalues of \(\pi_E\) are contained in \(\mathbb{Z}_l\). In this paper the authors propose a strategy which in addition makes use of higher powers \(l^n\) of “good primes” \(l\).
For the entire collection see [Zbl 0802.00018].

Reviewer: H.-G.Rück (Essen)

MSC:

14Q05	Computational aspects of algebraic curves
14G05	Rational points
14G15	Finite ground fields in algebraic geometry
11Y16	Number-theoretic algorithms; complexity

Keywords:

Schoof algorithm; number of rational points; \(\ell\)-adic Tate module; elliptic curve over a finite field; Frobenius endomorphism