Counting Points On Elliptic Curves - Schoof–Elkies–Atkin Algorithm

Schoof–Elkies–Atkin Algorithm

In the 1990s, Noam Elkies, followed by A. O. L. Atkin devised improvements to Schoof's basic algorithm by making a distinction among the primes that are used. A prime is called an Elkies prime if the characteristic equation of the Frobenius endomorphism, splits over . Otherwise is called an Atkin prime. Elkies primes are the key to improving the asymptotic complexity of Schoof's algorithm. Information obtained from the Atkin primes permits a further improvement which is asymptotically negligible but can be quite important in practice. The modification of Schoof's algorithm to use Elkies and Atkin primes is known as the Schoof–Elkies–Atkin (SEA) algorithm.

The status of a particular prime depends on the elliptic curve, and can be determined using the modular polynomial . If the univariate polynomial has a root in, where denotes the j-invariant of, then is an Elkies prime, and otherwise it is an Atkin prime. In the Elkies case, further computations involving modular polynomials are used to obtain a proper factor of the division polynomial . The degree of this factor is, whereas has degree .

Unlike Schoof's algorithm, the SEA algorithm is typically implemented as a probabilistic algorithm (of the Las Vegas type), so that root-finding and other operations can be performed more efficiently. Its computational complexity is dominated by the cost of computing the modular polynomials, but as these do not depend on, they may be computed once and reused. Under the heuristic assumption that there are sufficiently many small Elkies primes, and excluding the cost of computing modular polynomials, the asymptotic running time of the SEA algorithm is, where . Its space complexity is, but when precomputed modular polynomials are used this increases to .

Read more about this topic:  Counting Points On Elliptic Curves

Other related articles:

Schoof–Elkies–Atkin Algorithm - Implementations
... Schoof–Elkies–Atkin algorithm is implemented in the PARI/GP computer algebra system in the GP function ellap ...