Abstract: This paper studies binary algorithm of modular exponentiation，modifies the computing formula，and designs a novel fast algorithm of modular exponentiation based on binary partition table searching method.This algorithm divides the binary of exponent into many blocks，computes and stores modular exponentiation values of all cases of a binary block，whose first bit is 1 and other bits vary freely.Then traverses all binary bits from the most right to the most left，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 1s appear continuously，and can be divided into the same block.

Key words: RSA algorithm, modular exponentiation, binary algorithm, binary partition table search algorithm

摘要： 在方幂模的二进制快速算法基础上，进一步改写方幂模计算表达式，设计了一种基于查表法的二进制快速算法。算法将指数的二进制形式进行分组，提前计算并记忆一个二进制分组中首位为1其他位任意变化的所有情况下的方幂模结果，然后遍历指数的二进制形式，按照算法规则直接平方或连续多次平方后与事先记忆的值相乘，已经记忆的值不需要重复计算，从而减少了大量的乘法运算。算法分析和实验结果证明，基于查表法的方幂模二进制快速算法比二进制算法减少了乘法次数，尤其指数二进制形式中有大量1连续出现或相对连续出现（同一分组内有两位以上为1）的情况下算法效率比二进制算法有大幅度提高。

关键词: RSA算法, 方幂模, 二进制算法, 二进制分组查表法