Content deleted Content added
Clarified the role of the modular polynomials (which was incorrect), and added a link to Schoof's JNTB paper. |
SEA: Add ref to free implementation. |
||
Line 7:
In the case of an Atkin prime, we can gain some information from the factorization pattern of <math>\Phi_l(X,j(E))</math> in <math>\mathbb{F}_l[X]</math>, which constrains the possibilities for the number of points modulo <math>l</math>, but the asymptotic complexity of the algorithm depends entirely on the Elkies primes. Provided there are sufficiently many small Elkies primes (on average, we expect half the primes <math>l</math> to be Elkies primes), this results in a reduction in the running time. The resulting algorithm is probabilistic (of [[Las Vegas algorithm|Las Vegas]] type), and its expected running time is, heuristically, <math>\tilde{O}(\log^4 q)</math>, making it more efficient in practice than Schoof's algorithm.
{{reflist}}
==Implementations==
Schoof–Elkies–Atkin algorithm is implemented in the [[PARI/GP]] computer algebra system in the GP function ellap.
==External links==
| |||