Partitioned Computation to Accelerate Scalar Multiplication for Elliptic Curve Cryptosystems

The scalar multiplication is the dominant operation in Elliptic Curve Cryptosystems (ECC). It consists of a series of point additions and point doublings. A number of algorithms have been proposed to accelerate the scalar multiplication. Most of the algorithms demand high complexity which makes scalar multiplication hard to implement. In this paper, we propose an efficient algorithm for computing scalar multiplication based on partitioning scalar and propositional logic theory to address the trade-offs between speed and complexity. Our algorithm remains low complexity compared to existing accelerated scalar multiplication algorithms, whilst it is suitable for parallel processing systems.