一种改进的Montgomery模乘快速算法  

An Improved Fast Montgomery Multiplication Algorithm

作　　者：孔凡玉[1] 于佳[1] 李大兴[1] 

机构地区：[1]山东大学网络信息安全研究所,济南250100

出　　处：《计算机工程》2005年第8期1-3,9,共4页Computer Engineering

摘　　要：利用Karatsuba-Ofman算法的思想,改进了Montgomery模乘的CIOS实现算法:一方面,改进后的CIOS算法在时间效率上有较大提高,减少的乘法次数比率接近25%;另一方面,改进后的算法具有更好的并行性,能够实现两个乘法器的并行结构,适合于设计高速的RSA密码专用芯片。Montgomery algorithm is one of the most efficient algorithms implementing long integer modular multiplication in RSAcryptosystem. The CIOS method of Montgomery algorithm is improved via the idea of Karatsuba-Ofman algorithm,: the decrease rate amounts to nearly 25%. Furthermore, the improved CIOS algorithm can be implemented with parallel processing of two independent multiplications and is well suited to designing high-speed RSA crypto-chips.

关 键 词：RSA密码体制 MONTGOMERY模乘 CIOS算法 Karatsuba-Ofman算法 

分 类 号：TP309[自动化与计算机技术—计算机系统结构]