Generalized division polynomials

Authors

  • Takakazu Satoh

DOI:

https://doi.org/10.7146/math.scand.a-14436

Abstract

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 ÷ψα=PKer[α][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