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

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