Schoof–Elkies–Atkin algorithm: Difference between revisions

Revision as of 03:10, 15 March 2013

Revision as of 15:47, 20 April 2013

Line 2:

==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-AtkinSchoof–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 [[Classical modular curve|modular polynomials]] <math>\Phi_l(X,Y)</math> that parametrize pairs of <math>l</math>-[[isogeny|isogenous]] elliptic curves in terms of their [[j-invariant|j-invariants]]s (in practice alternative modular polynomials may also be used but for the same purpose).

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.

Line 17:

* [http://www.esat.kuleuven.ac.be/cosic/eurocrypt2000/pdf/fre-sea.pdf "The Schoof-Elkies-Atkin Algorithm in Characteristic 2"]

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

{{crypto-stub}}

[[Category:Asymmetric-key algorithms]]

[[Category:Elliptic curve cryptography]]