Content deleted Content added
m →Introduction: LaTeX spacing clean up, replaced: \, </math> → </math> using AWB |
m reduce verbosity |
||
Line 157:
In the 1990s, [[Noam Elkies]], followed by [[A. O. L. Atkin]], devised improvements to Schoof's basic algorithm by restricting the set of primes <math>S = \{l_1, \ldots, l_s\}</math> considered before 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 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 are able to work with a polynomial that has lower degree than the corresponding division polynomial: <math>O(l)</math> rather than <math>O(l^2)</math>. For efficient implementation, probabilistic root-finding algorithms are used, which makes this a [[Las Vegas algorithm]] rather than a deterministic algorithm.
Under the heuristic assumption that approximately half of the primes up to an <math>O(\log q)</math> bound are Elkies primes, this yields an algorithm that is more efficient than Schoof's, with an expected running time of <math>O(\log^6 q)</math> using naive arithmetic, and <math>\tilde{O}(\log^4 q)</math> using fast arithmetic.
==Implementations==
| |||