Content deleted Content added
→Details: - Corrected a link |
Corrected complexity estimate for the SEA algorithm, noting that it relies on heuristic assumptions and that it is a probabilistic algorithm. |
||
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 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 form]]s and an interpretation of [[Elliptic curve#Elliptic curves over the complex numbers|elliptic curves over the complex numbers]] as lattices. 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>).
==References==
| |||