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$
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$
  • $\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$ – Calodeon Nov 6 '14 at 10:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.