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

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)


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