Abstract
<p> We present several new algorithms to evaluate modular polynomials of level <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="script l"> <mml:semantics> <mml:mi> ℓ </mml:mi> <mml:annotation encoding="application/x-tex">\ell</mml:annotation> </mml:semantics> </mml:math> </inline-formula> modulo a prime <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="p"> <mml:semantics> <mml:mi>p</mml:mi> <mml:annotation encoding="application/x-tex">p</mml:annotation> </mml:semantics> </mml:math> </inline-formula> on an input <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="j"> <mml:semantics> <mml:mi>j</mml:mi> <mml:annotation encoding="application/x-tex">j</mml:annotation> </mml:semantics> </mml:math> </inline-formula> . More precisely, we introduce two new generic algorithms, sharing the following similarities: they are based on a CRT approach; they make use of supersingular curves and the Deuring correspondence; and, their memory requirements are optimal. </p> <p> The first algorithm combines the ideas behind a hybrid algorithm of Sutherland in 2013 with a recent algorithm to compute modular polynomials using supersingular curves introduced in 2023 by Leroux. The complexity (holding around several plausible heuristic assumptions) of the resulting algorithm matches the <inline-formula content-type="math/tex"> <tex-math>\Tilde {O}(\ell ^3 \log ^{3} \ell + \ell \log p)</tex-math> </inline-formula> time complexity of the best known algorithm by Sutherland, but has an optimal memory requirement. </p> <p> Our second algorithm is based on a sub-algorithm that can evaluate modular polynomials efficiently on supersingular <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="j"> <mml:semantics> <mml:mi>j</mml:mi> <mml:annotation encoding="application/x-tex">j</mml:annotation> </mml:semantics> </mml:math> </inline-formula> -invariants defined over <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="double-struck upper F Subscript p"> <mml:semantics> <mml:msub> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="double-struck">F</mml:mi> </mml:mrow> <mml:mi>p</mml:mi> </mml:msub> <mml:annotation encoding="application/x-tex">\mathbb {F}_p</mml:annotation> </mml:semantics> </mml:math> </inline-formula> , and achieves heuristic complexity quadratic in both <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="script l"> <mml:semantics> <mml:mi> ℓ </mml:mi> <mml:annotation encoding="application/x-tex">\ell</mml:annotation> </mml:semantics> </mml:math> </inline-formula> and <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="log j"> <mml:semantics> <mml:mrow> <mml:mi>log</mml:mi> <mml:mo> </mml:mo> <mml:mi>j</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">\log j</mml:annotation> </mml:semantics> </mml:math> </inline-formula> , and linear in <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="log p"> <mml:semantics> <mml:mrow> <mml:mi>log</mml:mi> <mml:mo> </mml:mo> <mml:mi>p</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">\log p</mml:annotation> </mml:semantics> </mml:math> </inline-formula> . In particular, it is the first generic algorithm with optimal memory requirement to obtain a quadratic complexity in <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="script l"> <mml:semantics> <mml:mi> ℓ </mml:mi> <mml:annotation encoding="application/x-tex">\ell</mml:annotation> </mml:semantics> </mml:math> </inline-formula> . </p> <p>Additionally, we show how to adapt our method to the computation of other types of modular polynomials such as the one stemming from Weber’s function.</p> <p>Finally, we provide an optimised implementation of the two algorithms detailed in this paper, though we emphasise that various modules in our codebase may find applications outside their use in this paper.</p>