A Parallel Algorithm for Computing Simultaneous Inversions with Application to Elliptic Curve Scalar Multiplication
Palash Sarkar, Pradeep Kumar Mishra, Rana Barua · 2006
Montgomery's trick is a well known technique for performing simultaneous inversions of several field elements. However, this technique is a strictly sequential algorithm. Here the authors introduced a parallel algorithm for performing simultaneous inversions of several finite field elements. The algorithm uses a binary tree and can perform inversions of 2/sup r/ elements using 3/spl times/2/sup r-1/ multipliers in (r + 1) multiplication rounds and one inversion round. The authors also described how to modify the algorithm when less number of multipliers is available. This parallel algorithm is used to obtain a new parallel algorithm for elliptic curve scalar multiplication using a fixed base point. The scalar multiplication algorithm is resistant against simple power analysis (SPA) and can be implemented with different number of multipliers (2,4,8,...). Results show that implementation with 2 multipliers can lead to almost 40% speed-up over previously best known sequential SPA resistant algorithm.