We know the ¡§signed-digit recoding algorithm¡¨ has less occurrence probability of the nonzero digit than original binary number representation. The goal of study time-efficient and space-efficient algorithms for modular arithmetic comes from the applications in modern cryptography, such as RSA cryptography and El-Gamal cryptography. Taking the RSA cryptography for example, the public and private keys are functions of a pair of prime numbers, and the encryption and decryption operations are accomplished by modular exponentiation. Fast modular exponentiation algorithms are often considered of practical significance in RSA cryptosystem. By using the technique of recording the common parts in the folded sub strings can improve the efficiency of the binary algorithm, thus can effective reduce the computational complexity of modular exponentiation.
展开▼
