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},
note = {\url{https://eprint.iacr.org/2002/179}},
url = {https://eprint.iacr.org/2002/179}
}
