A parallel algorithm for computing simultaneous inversions with application to elliptic curve scalar multiplication

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^r elements using 3times2^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