Efficient Modular Exponentiation with Three-Moduli (2^{n}卤1,2^{n}+3)

摘要

Modular exponentiation is the basic computation for most public key cryptosystems and digital signal processing. A new signed binary representation (SBR) of operand is presented, which has less weight than NAF when modulus is one of moduli (2^{n}卤1,2^{n}+3). The speed of modular squaring with three-moduli (2^{n}卤1,2^{n}+3) can be improved using the new SBR by reducing partial products and carries. Based on the result, the speed of computation of modular exponentiation using the new SBR may double that of NAF method for some exponents. According to theoretical analyses and experiment comparing to the other methods mentioned in this paper, the new SBR could improve the speed of modular exponentiation efficiently. Moreover, the SBR of integer can be widely used in secure communication and DSP system.