Computing Division Polynomials
James McKee · Mathematics of Computation · 1994
Recurrence relations for the coefficients of the nth division polynomial for elliptic curves are presented. These provide an algorithm for computing the general division polynomial without using polynomial multiplications; also a bound is given for the coefficients, and their general shape is revealed, with a means for computing the coefficients as explicit functions of n.