
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 ModularMultiplication Algorithm Using Lookahead Determination
Hikaru MORITA ChungHuang YANG
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E76A
No.1
pp.7077 Publication Date: 1993/01/25 Online ISSN:
DOI: Print ISSN: 09168508 Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security) Category: Keyword: modular multiplication, multiprecision arithmetic, smart card, digital signature, Robertson diagram,
Full Text: PDF>>
Summary:
This paper presents an efficient multiprecision modularmultiplication algorithm which minimizes the calculation RAM space required when implementing publickey schemes with software on generalpurpose computers including smart cards and personal computers. Many modularmultiplication algorithms cannot be efficiently realized on small systems due to their high RAM consumption. The Montgomery algorithm, which can rapidly perform modular multiplication, has received a lot of attention. Unfortunately, the Montgomery algorithm is difficult to implement, especially in smart cards which have extremely limited RAM space. Furthermore, when the modulus of modular multiplication is frequently changed, or when the number of permissible repeated modular multiplications is small, pre and postprocessing operations such as conversion from/to the Montgomery space become wasteful. The proposed algorithm avoids these problems because it requires only half the RAM space and no pre and postprocessing operations. The algorithm is a radical extension to the approximation methods that use the most significant bits and our newly proposed lookahead determination method. This paper gives a proof of the completeness of this method, describes implementation results using a smart card, introduces a theory supported by the results, and considers the optimal technique to enhance the speed of this method.

