A Fast Modular Exponentiation Algorithm


IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E74-A   No.8   pp.2136-2142
Publication Date: 1991/08/25
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Issue on Cryptography and Information Security)

Full Text: PDF(475.4KB)>>
Buy this Article

Most number-theoretic cryptosystems are constructed based on a modular exponentiation, which requires a large number of processing steps. Therefore, one of the most significant problems in cryptographic research is how to reduce the time needed to carry out a modular exponentiation operation. This paper proposes an improved modular exponentiation algorithm using a new table-look-up method. On executing a modular exponentiation computation, first, it must be decomposed efficiently into a series of modular multiplications. For this decomposition, the Binary method is used in this paper. When the Binary method is so implemented as to process the exponent in the-most-significant-bit-first manner, multiplier M, as well as modulus N, can also be considered as a common constant in 1/3 of the decomposed modular multiplications. Thus, with some additional procedure, one can compute beforehand the residues concerning M and N. This makes it possible to process the multiplication and reduction simultaneously. This algorithm is faster than conventional ones which take into account only that the modulus N can be considered a constant. The effectiveness of the proposed method is investigated with an evaluation model proposed in this paper and evaluated by software implemented on a engineering workstation and on a digital signal processor. The evaluation model indicates that the proposed method reduces the execution time by 17% compared with a conventional table-look-up method, if bit length k of modulus N is sufficiently large. The corresponding figure in the computer simulation is 14% for k=512.