Content deleted Content added
No edit summary |
m →Implementations: gr |
||
| (20 intermediate revisions by 16 users not shown) | |||
Line 1:
The '''Schoof–Elkies–Atkin algorithm (SEA)''' is an [[algorithm]] used for finding the [[order (group theory)|order]] of or calculating the number of points on an [[elliptic curve]] over a [[finite field]]. Its primary application is in [[elliptic curve cryptography]]. The algorithm is an extension of [[Schoof's algorithm]] by [[Noam Elkies]] and [[A. O. L. Atkin]] to significantly improve its efficiency (under heuristic assumptions).
==Details==
The Elkies-Atkin extension to [[Schoof's algorithm]] works by restricting the set of primes <math>S = \{l_1, \ldots, l_s\}</math> considered to primes of a certain kind. These came to be called Elkies primes and Atkin primes respectively. A prime <math>l</math> is called an Elkies prime if the characteristic equation: <math>\phi^2-t\phi+ q = 0</math> splits over <math>\mathbb{F}_l</math>, while an Atkin prime is a prime that is not an Elkies prime. Atkin showed how to combine information obtained from the Atkin primes with the information obtained from Elkies primes to produce an efficient algorithm, which came to be known as the
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.
▲The Elkies-Atkin extension to Schoof's algorithm works by restricting the set of primes <math>S = \{l_1, \ldots, l_s\}</math> considered to primes of a certain kind. These came to be called Elkies primes and Atkin primes respectively. A prime <math>l</math> is called an Elkies prime if the characteristic equation: <math>\phi^2-t\phi+ q = 0</math> splits over <math>\mathbb{F}_l</math>, while an Atkin prime is a prime that is not an Elkies prime. Atkin showed how to combine information obtained from the Atkin primes with the information obtained from Elkies primes to produce an efficient algorithm, which came to be known as the Schoof-Elkies-Atkin algorithm. The first problem to address is to determine whether a given prime is Elkies or Atkin. In order to do so, we make use of modular polynomials, which come from the study of modular forms and an interpretation of elliptic curves over the complex numbers as lattices(link). Once we have determined which case we are in, instead of using Division Polynomials, we proceed by working modulo the modular polynomials <math>f_l</math> which have a lower degree than the corresponding division polynomial <math>\psi_l</math> (degree <math>O(l)</math> rather than <math>O(l^2)</math>). This results in a further reduction in the running time, giving us an algorithm more efficient than Schoof's, with complexity <math>O(\log^6 q)</math><ref>C. Peters: Counting ponts on elliptic curves over <math>\mathbb{F}_q</math>. Available at http://www.win.tue.nl/~cpeters/presentations/2008-eccs.pdf</ref>.
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"]
* [
{{Algebraic curves navbox}}
{{DEFAULTSORT:Schoof-Elkies-Atkin algorithm}}
[[Category:Asymmetric-key
[[Category:Elliptic curve cryptography]]
[[Category:Group theory]]
[[Category:Finite fields]]
[[Category:Number theory]]
| |||