
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

A Fast Modular Exponentiation Algorithm
Shinichi KAWAMURA Kyoko TAKABAYASHI Atsushi SHIMBO
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E74A
No.8
pp.21362142 Publication Date: 1991/08/25
Online ISSN:
DOI:
Print ISSN: 09168508 Type of Manuscript: Special Section PAPER (Special Issue on Cryptography and Information Security) Category: Keyword:
Full Text: PDF(475.4KB)>>
Summary:
Most numbertheoretic 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 tablelookup 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 themostsignificantbitfirst 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 tablelookup method, if bit length k of modulus N is sufficiently large. The corresponding figure in the computer simulation is 14% for k=512.

