International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: Parallel Algorithm for Multiplication on Elliptic Curves

Authors:
Juan Manuel Garcia Garcia
Rolando Menchaca Garcia
Download:
URL: http://eprint.iacr.org/2002/179
Search ePrint
Search Google
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)$.
BibTeX
@misc{eprint-2002-11702,
  title={Parallel Algorithm for Multiplication on Elliptic Curves},
  booktitle={IACR Eprint archive},
  keywords={public-key cryptography / Elliptic curve cryptosystem},
  url={http://eprint.iacr.org/2002/179},
  note={Published on Proceedings of the ENC'01 jmgarcia@sekureit.com 12010 received 18 Nov 2002, last revised 18 Nov 2002},
  author={Juan Manuel Garcia Garcia and Rolando Menchaca Garcia},
  year=2002
}