一种适合流水线结构的改进FIOS模乘算法研究  

An improved FIOS Montgomery algorithm for pipeline structure

作　　者：邵奇[1] 刘红明[1] 

机构地区：[1]上海交通大学芯片与系统研究中心,上海200240

出　　处：《信息技术》2014年第4期92-95,99,共5页Information Technology

摘　　要：SOS、CIOS、FIOS、FIPS、CIHS是Montgomery模乘算法的5个基本实现方法,其中CIOS方法一直被认为是综合最优的算法。但已经有人提出了一种改进的IFIOS算法,并用实验证明其比常用的CIOS算法有优势。首先分析了CIOS、FIOS和IFIOS实现方法,通过进位单元的重复利用和减少存储单元,提出了一种改进的IIFIOS算法。然后根据IIFIOS算法的流程,让前后两个部分并行执行,提出了适合流水线结构的改进。最后,实验结果和理论分析表明,IIFIOS软件算法有效提升了算法性能,并指出其在硬件实现上也具有一定优势。SOS, CIOS, FIOS, FIPS and CIHS are the five implementation methods of Montgomery multiplication algorithm, and CIOS is always considered of the most efficient. An improved method named IFIOS has been given, which has been proved superior to CIOS by experimentation. Firstly, CIOS, FIOS and IFIOS are been analyzed, and IIFIOS an improved method is put forward by recycling carry unit and reduci to make it suit for ng storage. According the procedure of IIFIOS, let the two parts executed in parallel pipeline structure. IIFOS improves the performance in software implementation according to this analysis and experimentation, and also has an advantage in implementation of hardware.

关 键 词：Montgomery模乘算法 FIOS 流水线结构 

分 类 号：TP393.08[自动化与计算机技术—计算机应用技术]