Small scalar multiplication on Weierstrass curves using division polynomials

This paper deals with elliptic curves in the short Weierstrass form over large prime fields and presents algorithms for computing small odd multiples of a given point $P$ on a curve. Our algorithms make use of division polynomials and are more efficient than the naive algorithm based on repeated additions with $2P$. We show how to perform scalar multiplication in the variable base settings using the precomputed small multiples. By employing the window method and avoiding conditional branches, we achieve the constant-time property for the final scalar multiplication algorithm. Small multiples are computed in either Jacobian or affine coordinates. To obtain affine coordinates, we use Montgomery's trick of simultaneous multiplicative inversion of several field elements. The conversion to affine coordinates slows down the precomputations but speeds up the main scalar multiplication loop. We show that the conversion makes sense and gives an overall performance boost in practical settings.