## 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)

### MSC:

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