Generalized division polynomials - Satoh, Takakazu (MATHEMATICA SCANDINAVICA, 2004)
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 αO_F so that there exists a rational function ψ_α satisfying ψ_α=_PKer[α][P] - N_F /Q(α)[O ] where [α ] is the multiplication by α map. We give an algorithm to compute ψ_α based on recurrence formulas among these functions. We prove that the time complexity of this algorithm is O(N_F/Q(α )^2+ε) bit operations under an FFT based multiplication algorithm as N_F /Q(α ) tends to infinity for the fixed E.