효율적인 다중 멱승 알고리즘과 그 응용
Efficient Multi-Exponentiation and Its Application
0
조회
0
다운로드
0
인용
0
참고문헌
초록
다수의 멱승의 곱을 계산하는 효율적인 다중 멱승 알고리즘은 다양한 암호 프로토콜의 성능 향상을 위해 유용하게 사용될 수 있다. 본 논문에서는 4가지의 서로 다른 다중 멱승 알고리즘을 기술하고 그 효율성을 비교 분석한다. 각 알고리즘은 곱해지는 멱승의 수에 따라 가장 효율적인 영역들이 있으며, 각 영역에서 최선의 알고리즘을 이용하는 경우 기본적인 이진 알고리즘을 사용하는 경우에 비해 2~4배 정도의 성능향상을 얻을 수 있고, 각각의 멱승을 독립적으로 계산하는 경우에 비해서는 2~10배 정도의 성능향상을 얻을 수 있다.
Abstract
This paper deals with efficient algorithms for computing a product of n distinct powers in a group(called multi-exponentiation). Four different algorithms are presented and analyzed, each of which has its own range of n for best performance. Using the best performing algorithm for n ranging from 2 to several thousands, one can achieve 2 to 4 times speed-up compared to the baseline binary algorithm and 2 to 10 times speed-up compared to individual exponentiation.