### Abstract

In this paper we produce a practical and efficient algorithm to find a decomposition of type n = ∑_{i=1}^{k}2^{si}3 ^{ti}, s^{i} t^{i} ∈ ℕ ∪ {0} with k ≤ (c +o(1)) log n/log log n . It is conjectured that one can take c = 2 above. Then this decomposition is refined into an effective scalar multiplication algorithm to compute nP on some supersingular elliptic curves of characteristic 3 with running time bounded by O (log n/log log n) and essentially no storage. To our knowledge, this is the first instance of a scalar multiplication algorithm that requires o(log n) curve operations on an elliptic curve over double struck F sign_{q}, with log q ≈ log n and uses comparable storage as in the standard double-and-add algorithm. This leads to an efficient algorithm very useful for cryptographic protocols based on supersingular curves. This is for example the case of the well-studied (in the past four years) identity based schemes. The method carries over to any supersingular curve of fixed characteristic.

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

Title of host publication | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |

Pages | 171-182 |

Number of pages | 12 |

DOIs | |

Publication status | Published - Dec 1 2005 |

Event | 1st International Conference on Cryptology in Malaysia on Progress in Cryptology - Mycrypt 2005 - Kuala Lumpur, Malaysia Duration: Sep 28 2005 → Sep 30 2005 |

### Publication series

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

Volume | 3715 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Other

Other | 1st International Conference on Cryptology in Malaysia on Progress in Cryptology - Mycrypt 2005 |
---|---|

Country | Malaysia |

City | Kuala Lumpur |

Period | 9/28/05 → 9/30/05 |

### Keywords

- Exponentiation algorithms
- Integer decomposition

### ASJC Scopus subject areas

- Theoretical Computer Science
- Computer Science(all)

## Fingerprint Dive into the research topics of 'An analysis of double base number systems and a sublinear scalar multiplication algorithm'. Together they form a unique fingerprint.

## Cite this

*Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)*(pp. 171-182). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3715 LNCS). https://doi.org/10.1007/11554868_12