### Abstract

In most algorithms involving elliptic curves, the most expensive part consists in computing multiples of points. This paper investigates how to extend the τ-adic expansion from Koblitz curves to a larger class of curves defined over a prime field having an efficiently-computable endomorphism φ in order to perform an efficient point multiplication with efficiency similar to Solinas' approach presented at CRYPTO '97. Furthermore, many elliptic curve cryptosystems require the computation of k_{0}P + k_{1}Q. Following the work of Solinas on the Joint Sparse Form, we introduce the notion of φ-Joint Sparse Form which combines the advantages of a φ-expansion with the additional speedup of the Joint Sparse Form. We also present an efficient algorithm to obtain the φ-Joint Sparse Form. Then, the double exponentiation can be done using the φ endomorphism instead of doubling, resulting in an average of l applications of φ and l/2 additions, where l is the size of the k_{i}'s. This results in an important speed-up when the computation of φ is particularly effective, as in the case of Koblitz curves.

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

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

Editors | Eli Biham |

Publisher | Springer Verlag |

Pages | 388-400 |

Number of pages | 13 |

ISBN (Print) | 3540140395, 9783540140399 |

DOIs | |

Publication status | Published - 2003 |

### Publication series

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

Volume | 2656 |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Keywords

- Elliptic curves
- Fast endomorphisms
- Joint Sparse Form

### ASJC Scopus subject areas

- Theoretical Computer Science
- Computer Science(all)

## Fingerprint Dive into the research topics of 'Improved algorithms for efficient arithmetic on elliptic curves using fast endomorphisms'. 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. 388-400). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2656). Springer Verlag. https://doi.org/10.1007/3-540-39200-9_24