Faster scalar multiplication on koblitz curves combining point halving with the frobenius endomorphism

Roberto Maria Avanzi, Mathieu Ciet, Francesco Sica

Research output: Chapter in Book/Report/Conference proceedingChapter

20 Citations (Scopus)

Abstract

Let E be an elliptic curve defined over F2n. The inverse operation of point doubling, called point halving, can be done up to three times as fast as doubling. Some authors have therefore proposed to perform a scalar multiplication by an "halve-and-add" algorithm, which is faster than the classical double-and-add method. If the coefficients of the equation defining the curve lie in a small subfield of F2n, one can use the Frobenius endomorphism τ of the field extension to replace doublings. Since the cost of τ is negligible if normal bases are used, the scalar multiplication is written in "base τ" and the resulting "τ-and-add" algorithm gives very good performance. For elliptic Koblitz curves, this work combines the two ideas for the first time to achieve a novel decomposition of the scalar. This gives a new scalar multiplication algorithm which is up to 14.29% faster than the Frobenius method, without any additional precomputation.

Original languageEnglish
Title of host publicationLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
EditorsFeng Bao, Robert Deng, Jianying Zhou
PublisherSpringer Verlag
Pages28-40
Number of pages13
ISBN (Print)3540210180, 9783540210184
DOIs
Publication statusPublished - 2004

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2947
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Keywords

  • Integer decomposition
  • Koblitz curves
  • Point halving
  • Scalar multiplication
  • τ-adic expansion

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Faster scalar multiplication on koblitz curves combining point halving with the frobenius endomorphism'. Together they form a unique fingerprint.

Cite this