Generalized division polynomials
DOI:
https://doi.org/10.7146/math.scand.a-14436Abstract
Let E be an elliptic curve with complex multiplication by the ring OF of integers of an imaginary quadratic field F. We give an explicit condition on α∈OF so that there exists a rational function ψα satisfying ÷ψα=∑P∈Ker[α][P]−NF/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(NF/Q(α)2+ε) bit operations under an FFT based multiplication algorithm as NF/Q(α) tends to infinity for the fixed E.Downloads
Published
2004-06-01
How to Cite
Satoh, T. (2004). Generalized division polynomials. MATHEMATICA SCANDINAVICA, 94(2), 161–184. https://doi.org/10.7146/math.scand.a-14436
Issue
Section
Articles