期刊名称：International Journal of Security and Its Applications
印刷版ISSN：1738-9976
出版年度：2014
卷号：8
期号：4
页码：171-182
DOI：10.14257/ijsia.2014.8.4.16
出版社：SERSC
摘要：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.
