원문정보
초록
영어
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 (NAFw) 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 NAFw 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 NAFw some extra memory are needed with some restriction for w value.
목차
1. Introduction
2. Background
2.1. The Pairing
3. Miller’s Algorithm
3.1. Implementation
4. A modified Miller's Algorithm
4.1 . Miller's Algorithm with the NAF
5.1 . Miller’s Algorithm with the NAFw
5.2. Performance Comparison
6. Conclusion
References