Optimizing the computing of pairing with Miller's algorithm
Siham Ezzouak, Mohammed El Amrani, Abdelmalek Azizi · International Journal of Security and Its Applications · 2014
The Miller's algorithm is the best known algorithm for computing pairing.For this reason, numerous optimizations are applied to this algorithm.One of them is for making the basic loop of Miller's algorithm quicker with efficient arithmetic.In this paper, we try to do this by using Non Adjacent Form (NAF) and the window NAF (NAF w ) instead of the binary form of the key in the original Miller's algorithm.We show how this improvement can reduce the number of addition steps by 1/6 in the NAF representation or 1/2(w+1) in the NAF w where w is the size of the window in the NAF.Thereby both methods speed up Miller for efficient pairing implementation over extension field but with the NAF w some extra memory are needed with some restriction for w value.