CAJ | 학술논문

滑动窗口法是计算大数模幂问题应用最广泛的方法之一，然而针对此方法复杂度的精确理论分析却十分稀少。在计算效率方面，当窗口选择过大时，预计算量呈指数型增长。针对这2个问题，利用马尔可夫状态转移矩阵对滑动窗口法进行效率分析，给出大数模幂计算在二进制编码下滑动窗口法的精确复杂度表示，其理论值与实际值在各情况下误差绝对值不超过0.1次模乘。同时提出一种利用加法链进行预计算的思想，给出一种计算机执行简单可行的求加法序列的算法，用于求解由多个给定值构成的加法链。实验结果证明，该算法能够提高窗口选择过大时的计算效率，并可用于同一信息的多方发送等。
활동창구법시계산대수모멱문제응용최엄범적방법지일，연이침대차방법복잡도적정학이론분석각십분희소。재계산효솔방면，당창구선택과대시，예계산량정지수형증장。침대저2개문제，이용마이가부상태전이구진대활동창구법진행효솔분석，급출대수모멱계산재이진제편마하활동창구법적정학복잡도표시，기이론치여실제치재각정황하오차절대치불초과0.1차모승。동시제출일충이용가법련진행예계산적사상，급출일충계산궤집행간단가행적구가법서렬적산법，용우구해유다개급정치구성적가법련。실험결과증명，해산법능구제고창구선택과대시적계산효솔，병가용우동일신식적다방발송등。
Sliding window method is one of the most widely used methods for exponentiation, but analysis on its exact computational complexity are few. And when the window size becomes bigger, the total of precomputations grows exponentially. An analysis of the exact complexity of sliding window method with Markov transfer matrix is presented. It presents an expression of the exact complexity in binary code. The difference between theoretical and experimental values is less than 0.1 time of modular multiplication. After that, a method with addition chain passing all given values in precomputation is proposed. It generates an algorithm which is computationally feasible for computer implementation. Experimental result shows that this method improves the efficiency greatly when the window size is big. This thought can also be used in the case of one message sending to many clients.