基于Karatsuba递归思想的Montgomery模乘算法  

A novel Montgomery modular multiplication algorithm based on Karatsuba recursive idea

作　　者：羊红光[1,2] 黄世中[1,3] 张利民[4] 

机构地区：[1]河北省科学院应用数学研究所,河北石家庄050081 [2]石家庄冀科双实科技公司,河北石家庄050081 [3]河北省数字研究中心,河北石家庄050016 [4]衡水学院数学与计算机学院,河北衡水053000

出　　处：《微型机与应用》2010年第16期21-23,共3页Microcomputer & Its Applications

基　　金：河北省自然科学基金数学研究专项(08M009);河北省科学院重大科技攻关项目(D2009614)

摘　　要：采用大数的高基表示方法和Karatsuba递归思想改进了Montgomery模乘中的IFIOS实现算法,该算法可以应用于RSA公钥体制下的模乘法器的设计。模乘运算的速度决定了公钥加密系统和众多通信系统的系统性能,通过与IFIOS算法的比较分析发现,改进后的算法具有使用的乘法次数少、并行性能高等优点,是一种适合设计硬件的高效算法。此算法也适用于其他公钥体制的加解密处理器。A high-radix technique and aratsuba recursive idea is employed to improve the IFIOS-Montgomery＇s algorithm, and the improved algorithm is adapted to design of modular multiplier for RSA cryptosystem. Modular multiplication operation is a key factor of determining performance system of publickey cryptography systems and most of communication systems. Compared with IFIOS algorithm, the improved algorithm require less multiplications and has a higher parallel performance. So the improved algorithm is an efficient algorithm suitable for hardware design and adapted to several public-key system encryption/decryption processors.

关 键 词：MONTGOMERY模乘 Karatsuba递归思想 IFIOS 

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