IEICE TRANSACTIONS on Fundamentals
A Modular-Multiplication Algorithm Using Lookahead Determination
Summary :
This paper presents an efficient multi-precision modular-multiplication algorithm which minimizes the calculation RAM space required when implementing public-key schemes with software on general-purpose computers including smart cards and personal computers. Many modular-multiplication 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 post-processing 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 post-processing 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.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E76-A No.1 pp.70-77
- Publication Date
- 1993/01/25
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- Special Section PAPER (Special Section on Cryptography and Information Security)
- Category
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Hikaru MORITA, Chung-Huang YANG, "A Modular-Multiplication Algorithm Using Lookahead Determination" in IEICE TRANSACTIONS on Fundamentals,
vol. E76-A, no. 1, pp. 70-77, January 1993, doi: .
Abstract: This paper presents an efficient multi-precision modular-multiplication algorithm which minimizes the calculation RAM space required when implementing public-key schemes with software on general-purpose computers including smart cards and personal computers. Many modular-multiplication 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 post-processing 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 post-processing 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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e76-a_1_70/_p
Copy
@ARTICLE{e76-a_1_70,
author={Hikaru MORITA, Chung-Huang YANG, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={A Modular-Multiplication Algorithm Using Lookahead Determination},
year={1993},
volume={E76-A},
number={1},
pages={70-77},
abstract={This paper presents an efficient multi-precision modular-multiplication algorithm which minimizes the calculation RAM space required when implementing public-key schemes with software on general-purpose computers including smart cards and personal computers. Many modular-multiplication 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 post-processing 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 post-processing 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.},
keywords={},
doi={},
ISSN={},
month={January},}
Copy
TY - JOUR
TI - A Modular-Multiplication Algorithm Using Lookahead Determination
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 70
EP - 77
AU - Hikaru MORITA
AU - Chung-Huang YANG
PY - 1993
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E76-A
IS - 1
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - January 1993
AB - This paper presents an efficient multi-precision modular-multiplication algorithm which minimizes the calculation RAM space required when implementing public-key schemes with software on general-purpose computers including smart cards and personal computers. Many modular-multiplication 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 post-processing 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 post-processing 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.
ER -
English
