Welcome to the resource topic for 2006/067
Title:
Scalar Multiplication on Koblitz Curves using Double Bases
Authors: Roberto Avanzi, Francesco Sica
Abstract:The paper is an examination of double-base decompositions of
integers n, namely expansions loosely of the form
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.
ePrint: https://eprint.iacr.org/2006/067
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .