7
$\begingroup$

The Schoof-Elkies-Atkin (SEA) algorithm (for counting points on elliptic curves over a finite field) performs computations over polynomials modulo some modular polynomials. Originally the "classical" modular polynomials (the minimum polynomial of the modular function $\tau \mapsto j(\ell \tau)$ for a given prime $\ell$). It turns out that the coefficients of this polynomial increase very fast with the prime $\ell$, so in practice other polynomials should be used. In the Handbook of Elliptic and Hyperelliptic Curve Cryptography (Cohen and Frey), they present the "canonical" modular polynomials, and apparently people also use the Weber modular polynomials (Genus 1 point counting records over prime fields), which have even smaller coefficients, but I cannot find any reference on how to use them. And people also talk about other polynomials (Atkin polynomials ?).

In all the descriptions of SEA I could find, they just use the classical version and add a side note "in practice we would use other polynomials".

So here is the question: is there any literature dealing with those alternatives of the classical modular polynomials? (comparing them, which one is the best in the context of SEA, and how to use them even though they don't give as much information as the classical one). Which ones are used in the state-of-the-art implementations of SEA and why? (e.g. in Magma).

$\endgroup$

1 Answer 1

3
$\begingroup$

Andrew Sutherland (in his paper On the evaluation of modular polynomials, where he documents the point counting record) refers to Section 7 of the paper by himself, Broker and Lauter (Modular polynomials via isogeny volcanos) as a good source for properties of other modular polynomials.

It looks like Weber modular polynomials are the most popular in general, since they are "smaller" by a factor of 1728 than the others. Sutherland's modification of the SEA algorithm (which was used to compute $\# E(\mathbb{F}_{p})$, where $p$ has $5011$ digits) used Weber modular polynomials. I would refer to Sutherland's computation as "state-of-the-art".

I've had a hard time figuring out whether the implementations of SEA in Magma, PARI/GP, and Sage use which modular polynomials. It looks to me like PARI/GP primarily uses Atkin modular polynomials.

$\endgroup$
1
  • $\begingroup$ It turns out that the Weber modular polynomials are not that suitable for practical applications (generating curves for cryptography), because they only work for curves whose discriminant D of the CM-field is 1 mod 8, which implies that 2 divides the order of the curve (bad, we want prime order to avoid small subgroup attacks). Therefore Atkin modular polynomials might be more suitable. But it seems they cannot be used in the same way, and again, I cannot find any reference! $\endgroup$ Commented Nov 6, 2014 at 10:47

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.