Anzeige
Erschienen in:
2006 | OriginalPaper | Buchkapitel
Scalar Multiplication on Koblitz Curves Using Double Bases
verfasst von : Roberto Avanzi, Francesco Sica
Erschienen in: Progress in Cryptology - VIETCRYPT 2006
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
The paper is an examination of double-base decompositions of integers
n
, namely expansions loosely of the form
$n = \sum_{i,j} \pm A^iB^j $
for some base {
A
,
B
}. This was examined in previous works [5,6], in the case when
A
,
B
lie in ℕ.
We show here how to extend the results of [5] 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. In view of combinatorial results, this is the best type of estimate with two bases, apart from the value of the constant in the
O
notation.