A MODULAR-MULTIPLICATION ALGORITHM USING LOOKAHEAD DETERMINATION

被引:0
作者
MORITA, H
YANG, CH
机构
关键词
MODULAR MULTIPLICATION; MULTI-PRECISION ARITHMETIC; SMART CARD; DIGITAL SIGNATURE; ROBERTSON DIAGRAM;
D O I
暂无
中图分类号
TP3 [计算技术、计算机技术];
学科分类号
0812 ;
摘要
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,(20),(6) 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(2),(4),(5),(19),(21),(22),(28) 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.
引用
收藏
页码:70 / 77
页数:8
相关论文
empty
未找到相关数据