Schoof–Elkies–Atkin algorithm: Difference between revisions

Revision as of 15:47, 20 April 2013

Latest revision as of 07:36, 6 May 2025

(10 intermediate revisions by 8 users not shown)

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}}

==Implementations==

The Schoof–Elkies–Atkin algorithm is implemented in the [[PARI/GP]] computer algebra system in the GP function ellap.

==External links==

* [http://archive.numdam.org/ARCHIVE/JTNB/JTNB_1995__7_1/JTNB_1995__7_1_219_0/JTNB_1995__7_1_219_0.pdf "Schoof: Counting points on elliptic curves over finite fields"]

* [http://mathworld.wolfram.com/Schoof-Elkies-AtkinAlgorithm.html article] on [[Mathworld]]]

* [http://www.ams.org/mcom/1998-67-223/S0025-5718-98-00962-4/home.html "Remarks on the Schoof-Elkies-Atkin algorithm"]

* [httphttps://www.esat.kuleuven.ac.be/cosic/eurocrypt2000publications/pdf/frearticle-sea403.pdf "The Schoof-Elkies-AtkinSEA Algorithm in Characteristic 2"]

{{Algebraic curves navbox}}

{{DEFAULTSORT:Schoof-Elkies-Atkin algorithm}}