### Abstract

The paper is an examination of double-base decompositions of integers n, namely expansions loosely of the form n = Σ_{i, j} ± A ^{i}B^{j} for some base {A, B}. This was examined in previous works [5,6], in the case when A, B lie in N. 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 (log n / log lgo n) 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.

Original language | English |
---|---|

Title of host publication | Progress in Cryptology, VIETCRYPT 2006 - 1st International Conference on Cryptology in Vietnam, Revised Selected Papers |

Pages | 131-146 |

Number of pages | 16 |

DOIs | |

Publication status | Published - Dec 1 2006 |

Event | 1st International Conference on Cryptology in Vietnam, VIETCRYPT 2006 - Hanoi, Viet Nam Duration: Sep 25 2006 → Sep 28 2006 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 4341 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Other

Other | 1st International Conference on Cryptology in Vietnam, VIETCRYPT 2006 |
---|---|

Country | Viet Nam |

City | Hanoi |

Period | 9/25/06 → 9/28/06 |

### Keywords

- Double base number systems
- Elliptic curves
- Koblitz curves
- Scalar multiplication
- Sublinear algorithms

### ASJC Scopus subject areas

- Theoretical Computer Science
- Computer Science(all)

## Fingerprint Dive into the research topics of 'Scalar multiplication on Koblitz curves using double bases'. Together they form a unique fingerprint.

## Cite this

*Progress in Cryptology, VIETCRYPT 2006 - 1st International Conference on Cryptology in Vietnam, Revised Selected Papers*(pp. 131-146). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4341 LNCS). https://doi.org/10.1007/11958239-9