Class polynomials for nonholomorphic modular functions (Q898812)

This paper provides efficient algorithms to compute the Hilbert class polynomials (minimal polynomials) of singular moduli (values of the \(j\)-invariant at imaginary quadratic points of the Poincaré upper-half complex plane) of some nonholomorphic modular functions. These algorithms compute first the class polynomials modulo a set of primes and then they use the Chinese remainder theorem. Algorithm 1 (Section 3.1) computes the class polynomial \(H_D(\gamma;x)\), where \(D\) is an imaginary quadratic discriminant and \(\gamma\) a particular nonholomorphic function, see \textit{D. W. Masser} [Elliptic functions and transcendence. Berlin etc.: Springer-Verlag (1975; Zbl 0312.10023)]. Under the Generalized Riemann Hypothesis the computational complexity of Algorithm 1 is \(\widetilde{O}(|D|^{7/2})\) (Theorem 1.1). Algorithm 1 uses as a tool Algorithm 1.1, which computes the modular polynomial \(\phi_m\) modulo a prime \(p\) using the theory of \(l\)-isogeny volcanoes (connected components of the graph of \(l\)-isogenies of elliptic curves defined over a finite field \(F_q\), \(q=p^r\), \(l\neq p\)), approach developed by the third author et al. in a previous paper [Math. Comput. 81, No. 278, 1201--1231 (2012; Zbl 1267.11125)]. Algorithm 2 (Section 3.2) extends the scope of Algorithm 1 to a class of nonholomorphic modular functions (called \textit{good modular functions} in the paper). As an application Algorithm 3 (Section 3.3) computes the \textit{partition class polynomials} \(H_n^{\mathrm{part}}(x)\), defined by the two first authors in a previous paper [Adv. Math. 246, 198--219 (2013; Zbl 1304.11021)]. The expected running time of Algorithm 3 is \(\widetilde{O}(n^{5/2})\) and an example of execution of this algorithm is worked in detail in Section 4.