Content deleted Content added
Undid revision 715939556 by Sapphorain (talk) this is a mistake; O~ means something different than O. (It suppresses terms logarithmic in the main term.) |
→Details: explain O~ |
||
Line 5:
If the instantiated polynomial <math>\Phi_l(X,j(E))</math> has a root <math>j(E')</math> in <math>\mathbb{F}_q</math> then <math>l</math> is an Elkies prime, and we may compute a polynomial <math>f_l(X)</math> whose roots correspond to points in the kernel of the <math>l</math>-isogeny from <math>E</math> to <math>E'</math>. The polynomial <math>f_l</math> is a divisor of the corresponding [[Division polynomials|division polynomial]] used in Schoof's algorithm, and it has significantly lower degree, <math>O(l)</math> versus <math>O(l^2)</math>. For Elkies primes, this allows one to compute the number of points on <math>E</math> modulo <math>l</math> more efficiently than in Schoof's algorithm.
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. Here the <math>\tilde{O}</math> notation is a variant of [[big O notation]] that suppresses terms that are logarithmic in the main term of an expression.
{{reflist}}
| |||