[Resource Topic] 2002/179: Parallel Algorithm for Multiplication on Elliptic Curves

Welcome to the resource topic for 2002/179

Parallel Algorithm for Multiplication on Elliptic Curves

Authors: Juan Manuel Garcia Garcia, Rolando Menchaca Garcia


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

ePrint: https://eprint.iacr.org/2002/179

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .