CAJ | 학술논문

在方幂模的二进制快速算法基础上,进一步改写方幂模计算表达式,设计了一种基于查表法的二进制快速算法.算法将指数的二进制形式进行分组,提前计算并记忆一个二进制分组中首位为1其他位任意变化的所有情况下的方幂模结果,然后遍历指数的二进制形式,按照算法规则直接平方或连续多次平方后与事先记忆的值相乘,已经记忆的值不需要重复计算,从而减少了大量的乘法运算.算法分析和实验结果证明,基于查表法的方幂模二进制快速算法比二进制算法减少了乘法次数,尤其指教二进制形式中有大量1连续出现或相对连续出现(同一分组内有两位以上为1)的情况下算法效率比二进制算法有大幅度提高.
재방멱모적이진제쾌속산법기출상,진일보개사방멱모계산표체식,설계료일충기우사표법적이진제쾌속산법.산법장지수적이진제형식진행분조,제전계산병기억일개이진제분조중수위위1기타위임의변화적소유정황하적방멱모결과,연후편력지수적이진제형식,안조산법규칙직접평방혹련속다차평방후여사선기억적치상승,이경기억적치불수요중복계산,종이감소료대량적승법운산.산법분석화실험결과증명,기우사표법적방멱모이진제쾌속산법비이진제산법감소료승법차수,우기지교이진제형식중유대량1련속출현혹상대련속출현(동일분조내유량위이상위1)적정황하산법효솔비이진제산법유대폭도제고.
This paper studies binary algorithm of modular expenentiation,modifies the computing formula,and designs a novel fast algorithm of modular expenentiation based .on binary partition table searching method.This algorithm divides the binary of exponent into many blocks,computes and stores modular expenentiation values of all cases of a binary block,whose fn-st bit is 1 and other bits vary freely.Then traverses all binary bits from the most right to the most loft,computes the square or square and product of according value stored beforehand,according to algorithm rules.Because the stored value need not compute again,the times of product can be reduced a lot.Algorithm analysis and experiment results show that this algorithm is more efficient compared to binary algorithm of modular exponentiation,especially when a lot of ls appear continuously, and can be divided into the same block.