Cryptology ePrint Archive: Report 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)$.

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