According to R.A.Kazmi's dissertation "Isogenies and Cryptography" (Page 22), given an isogeny degree $l$, the Müller modular polynomials are defined as

$$G_l(x,y)=\sum_{r=0}^{l+1}\sum_{k=0}^{v}a_{r,k}x^ry^k\in\mathbb Z[x,y]$$

where $v=\frac{s(l-1)}{12}$, $s=\frac{12}{\gcd(l-1,12)}$, but the explanation of $a_{r,k}$ is missing. How can I compute them?

  • $\begingroup$ the calculation of the $a_{r,k}$'s from the modular form is complicated; there is a Sourceforce project that claims to do this, but I have the impression it is not maintained. $\endgroup$ – Carlo Beenakker May 3 '18 at 10:51

The definition of the coefficients $a_{r,k}$ is given by theorem III.17 on page 53 of "Elliptic curves in cryptography" by I.F. Blake, G. Seroussi, N.P. Smart (Cambridge University Press, 1999) (also on Google Books).

With $v,s,l$ as in the question, define $f(\tau) = \left( \dfrac {\eta(\tau)} {\eta(l\tau)} \right)^{2s}$, where $\eta$ is Dedekind's $\eta$ function. If $j$ is the invariant function (see page 47 of the quoted book), then there exist numbers $a_{r,k} \in \mathbb Z$ such that

$$\sum _{r=0} ^{l+1} \sum _{k=0} ^v a_{r,k} f(\tau)^r j(lt)^k =0 \ .$$

Now just formally replace $f(\tau)$ with $x$ and $j(l\tau)$ with $y$ to get $G_l(x,y)$.

Brief descriptions of the actual computation of these coefficients are given on page 54, and in "Counting the number of points on elliptic curves over finite fields of characteristic greater than three" by F. Lehmann, M. Maurer, V. Müller, V. Shoup.


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.