Paper 2006/067
Scalar Multiplication on Koblitz Curves using Double Bases
Roberto Avanzi and Francesco Sica
Abstract
The paper is an examination of doublebase decompositions of integers $n$, namely expansions loosely of the form $$ n = \sum_{i,j} A^iB^j $$ for some base $\{A,B\}$. This was examined in previous works in the case when $A,B$ lie in $\mathbb{N}$. On the positive side, we show how to extend previous results of to Koblitz curves over binary fields. Namely, we obtain a sublinear scalar algorithm to compute, given a generic positive integer $n$ and an elliptic curve point $P$, the point $nP$ in time $O\left(\frac{\log n}{\log\log n}\right)$ elliptic curve operations with essentially no storage, thus making the method asymptotically faster than any know scalar multiplication algorithm on Koblitz curves. On the negative side, we analyze scalar multiplication using double base numbers and show that on a generic elliptic curve over a finite field, we cannot expect a sublinear algorithm with double bases. Finally, we show that all algorithms used hitherto need at least $\frac{\log n}{\log\log n}$ curve operations.
Metadata
 Available format(s)
 PDF PS
 Category
 Implementation
 Publication info
 Published elsewhere. Unknown where it was published
 Keywords
 elliptic curve cryptosystemfast endomorphismsnumber theory
 Contact author(s)
 fsica @ mta ca
 History
 20060223: received
 Short URL
 https://ia.cr/2006/067
 License

CC BY
BibTeX
@misc{cryptoeprint:2006/067, author = {Roberto Avanzi and Francesco Sica}, title = {Scalar Multiplication on Koblitz Curves using Double Bases}, howpublished = {Cryptology ePrint Archive, Paper 2006/067}, year = {2006}, note = {\url{https://eprint.iacr.org/2006/067}}, url = {https://eprint.iacr.org/2006/067} }