Parallel Algorithm for Multiplication on Elliptic Curves

Juan Manuel Garcia Garcia; Rolando Menchaca Garcia

Paper 2002/179

Parallel Algorithm for Multiplication on Elliptic Curves

Juan Manuel Garcia Garcia and Rolando Menchaca Garcia

Abstract

Given a positive integer $n$ and a point $P$ on an elliptic curve $E$, the computation of $nP$, that is, the result of adding $n$ times the point $P$ to itself, called the \emph{scalar multiplication}, is the central operation of elliptic curve cryptosystems. We present an algorithm that, using $p$ processors, can compute $nP$ in time $O(\log n+H(n)/p+\log p)$, where $H(n)$ is the Hamming weight of $n$. Furthermore, if this algorithm is applied to Koblitz curves, the running time can be reduced to $O(H(n)/p+\log p)$.

Metadata

Available format(s): PDF PS
Category: Public-key cryptography
Publication info: Published elsewhere. Published on Proceedings of the ENC'01
Keywords: Elliptic curve cryptosystem
Contact author(s): jmgarcia @ sekureit com
History: 2002-11-21: received
Short URL: https://ia.cr/2002/179
License: CC BY

BibTeX

@misc{cryptoeprint:2002/179,
      author = {Juan Manuel Garcia Garcia and Rolando Menchaca Garcia},
      title = {Parallel Algorithm for Multiplication on Elliptic Curves},
      howpublished = {Cryptology {ePrint} Archive, Paper 2002/179},
      year = {2002},
      url = {https://eprint.iacr.org/2002/179}
}