Generalized division polynomials

Abstract

Let $E$ be an elliptic curve with complex multiplication by the ring $O_{F}$ of integers of an imaginary quadratic field $F$. We give an explicit condition on $\alpha\in O_{F}$ so that there exists a rational function $\psi_{\alpha}$ satisfying $\div\psi_{\alpha}=\sum_{P\in\mathrm{Ker}[\alpha]}[P] - N_{F /Q}(\alpha)[{\mathcal{O}}]$ where $[\alpha ]$ is the multiplication by $\alpha$ map. We give an algorithm to compute $\psi_{\alpha}$ based on recurrence formulas among these functions. We prove that the time complexity of this algorithm is $O(N_{F/Q}(\alpha )^{2+\varepsilon})$ bit operations under an FFT based multiplication algorithm as $N_{F /Q}(\alpha )$ tends to infinity for the fixed $E$.