Improving Miller’s Algorithm Using the NAF and the Window NAF

摘要

The Miller’s algorithm is the most commonly used algorithm for computing pairing. To efficiently implement the pairings, it is necessary to optimise the computation time for the Miller’s algorithm and the numbers of iterations. In this paper, we attempt to improve the original Miller’s algorithm by using Non Adjacent Form (NAF) and The window NAF (NAF_w). These representations allow one to reduce the number of iterations in the original Miller’s algorithm from l/2 to l/3 (NAF) or l/w+1 (NAF_w) where w is the size of the window in the NAF. Our approach is to replace the binary representation for the key by the NAF presentation or the NAF_w presentation in the Miller’s algorithm.