%Scalar multiplications are the basic operations in elliptic curve cryptosystems. The evaluation of a scalar multiplication can be sped up by using signed representations of the scalar. In exchange for the speed up, the precomputation of a series of points is required. While a lot of research has been done in the direction of signed representations, little attention has been paid to efficient methods to precompute the required points. Such methods are important since costly field inversions are involved in the precomputation. This paper presents a new method for the precomputation that requires only one single field inversion, independent of the number of points to precompute. The points to precompute are all odd points $[3]P, [5]P,\ldots, [2k-1]P$, $k \geq 2$ on an elliptic curve over $\mathbb{F}_p$. The proposed method benefits especially from a large ratios between inversions and multiplications as they occur on smart cards.
Category / Keywords: public-key cryptography / affine coordinates, elliptic curve cryptosystem, precomputation, scalar multiplication Publication Info: ACISP'07, LNCS 4586, Springer, 2007, pp. 245-258. Date: received 10 Jul 2007 Contact author: dahmen at cdc informatik tu-darmstadt de Available format(s): PDF | BibTeX Citation Version: 20070710:142135 (All versions of this report) Short URL: ia.cr/2007/268 Discussion forum: Show discussion | Start new discussion