Welcome to the resource topic for 2023/064
Title:
Computation of Hilbert class polynomials and modular polynomials from supersingular elliptic curves
Authors: 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.
ePrint: https://eprint.iacr.org/2023/064
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .