Paper 2023/064

Computation of Hilbert class polynomials and modular polynomials from supersingular elliptic curves

Antonin Leroux
Abstract

We present several new heuristic algorithms to compute class polynomials and modular polynomials modulo a prime $P$. For that, we revisit the idea of working with supersingular elliptic curves. The best known algorithms to this date are based on ordinary curves, due to the supposed inefficiency of the supersingular case. While this was true a decade ago, the recent advances in the study of supersingular curves through the Deuring correspondence motivated by isogeny-based cryptography has provided all the tools to perform the necessary tasks efficiently. Our main ingredients are two new heuristic algorithms to compute the $j$-invariants of supersingular curves having an endomorphism ring contained in some set of isomorphism class of maximal orders. The first one is derived easily from the existing tools of isogeny-based cryptography, while the second introduces new ideas to perform that task efficiently for a big number of maximal orders. From there, we obtain two main results. First, we show that we can associate these two algorithms with some operations over the quaternion algebra ramified at $P$ and infinity to compute directly Hilbert and modular polynomials $\mod P$. In that manner, we obtain the first algorithms to compute Hilbert (resp. modular) polynomials modulo $P$ for a good portion of all (resp. all) primes $P$ with a complexity in $O(\sqrt{|D|})$ for the discriminant $D$ (resp. $O(\ell^2)$ for the level $\ell$). Due to the (hidden) complexity dependency on $P$, these algorithms do not outperform the best known algorithms for all prime $P$ but they still provide an asymptotic improvement for a range of prime going up to a bound that is sub-exponential in $|D|$ (resp. $\ell$). Second, we revisit the CRT method for both class and modular polynomials. We show that applying our second heuristic algorithm over supersingular curves to the CRT approach yields the same asymptotic complexity as the best known algorithms based on ordinary curves and we argue that our new approach might be more efficient in practice. The situation appears especially promising for modular polynomials, as our approach reduces the asymptotic cost of elliptic curve operations by a linear factor in the level $\ell$. We obtain an algorithm whose asymptotic complexity is now fully dominated by linear algebra and standard polynomial arithmetic over finite fields.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint.
Keywords
Elliptic curves
Contact author(s)
antonin leroux @ polytechnique org
History
2023-01-20: approved
2023-01-20: received
See all versions
Short URL
https://ia.cr/2023/064
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/064,
      author = {Antonin Leroux},
      title = {Computation of Hilbert class polynomials and modular polynomials from supersingular elliptic curves},
      howpublished = {Cryptology ePrint Archive, Paper 2023/064},
      year = {2023},
      note = {\url{https://eprint.iacr.org/2023/064}},
      url = {https://eprint.iacr.org/2023/064}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.