Parallel Decomposition of Modular Exponentiation for RSA Cryptosystem
Shin-ichi Shimonaka, Naoki Takeda, Hiroshi Nagase · International Symposium on Information Theory and its Applications · 1994
RSA cryptosystem takes a long time to cipher and to decipher. This time consumption is caused by modular exponentiation. Hence, this paper describes about speeding up techniques of modular exponentiation on RSA cryptosystem. The key idea is to decompose modular exponentiation Me of a large digit integer M to multiple modular exponentiations of small digit integers. In the proposed method, we firstly select a cardinal number M', and divide M by M' (its quotient is again symbolized by M). If M does not equal 1, we square M by itself and decrease the value of e to e/2. Subsequently, we repeat the decomposition by cardinal numbers. If M equals 1 or exponent e equals 1, the algorithm terminates. Some numerical results are shown with considerations.