Parallelization Of The Number Of Elliptic Curve Multiplication

Being a important asymmetrical cryptography, Elliptic curve cryptography (ECC) is adopted by many famous international standardization organizations, and is widely used in commercial encryption. Scalar multiplication is the main operation in ECC. It determines the speed of encryption / decryption in ECC. Many studies were carried out on improving scalar multiplication, and many improved algorithms were presented. In this article, I present an algorithm based on parallelization.Firstly I present the basic mathematics of elliptic curves, and then present the elliptic curves defined on two finite fields, and then present the encryption schemas based on elliptic curves.Then I present the studies on improving scalar multiplication. Improving methods can be categorized into four classes, namely improving underlying operations, using another coordination system, improving addtion chains and improving some special elliptic curves.Then based on the analysis of running time of binary algorithm and its imroved variant, I present a parallel algorithm of scalar multiplication, and analyze the running time of that parallel algorithm.At last I design and implement a experimental system to test the performance of the parallel algorithm, and analyze the outcome of experiment. The data show that: restricted by the fact that the number of double operations is independent of the number of processors, the parallel algorithm is greatly affected by Double algorithm. Only when a efficient Double algorithm existes can the parallel algorithm greatly improve the speed of scalar multiplication. For example, when in Fp field, (the length of p is rangd from 192 to 256), and adopting the efficient Double algorithm, the parallel algorithm of 24-ary run on 4 processors can gain a speedup of about 76% than binary algorithm, and about 50% than sequentail 24-ary.