**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)$.

**Category / Keywords: **public-key cryptography / Elliptic curve cryptosystem

**Publication Info: **Published on Proceedings of the ENC'01

**Date: **received 18 Nov 2002, last revised 18 Nov 2002

**Contact author: **jmgarcia at sekureit com

**Available format(s): **Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

**Version: **20021121:235941 (All versions of this report)

**Short URL: **ia.cr/2002/179

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]