分割式Montgomery模乘运算的线性高基心动阵列新结构  

A Novel Systolic Linear Array Architecture for Partitioning Montgomery Modular Multiplication

作　　者：王冕[1] 周玉洁[1] 

机构地区：[1]信息工程大学信息工程学院信息研究系,郑州450002

出　　处：《计算机科学》2006年第1期184-187,共4页Computer Science

摘　　要：本文基于提高并行性、加速模乘的思想，利用分割操作数的方法，提出了分割式Montgomery模乘算法（PMMM），并且基于C．D.Walter发明的心动阵列结构，提出了新的线性高基心动阵列模乘结构，较好地实现了PMMM。对于基r（r=2^w）的n位模乘运算，Walter使用（n＋1）（n＋2）个PF来实现Montgomery模乘，我们用n＋2个PE实现Montgomery模乘，最大并行性为Walter的2倍。将此结构应用于模幂运算，仅需一次预计算便可使得非平方模乘的输入输出延迟为walter中的1/2，且平方模乘延迟与其相当，从而提高了模幂的运算速度。当然，考虑到对速度和硬件资源的不同需求，我们也给出了使用n/2＋1个PE来计算模乘、模幂的实现算法，并做出了相应的数据分析。A new partitioning Montgomery modular multiplication algorithm（PMMM）is proposed in this paper together with a hardware architecture proper for it to get high simultaneity and performance. And the architecture is a liner highindex systolic array one that is refined from the one proposed by C. D. Walter^[3]. While Walter^[3] used （n=1）（n=2）PEs to accomplish Montgomery modular multiplication, we use n＋ 2 PEs, and the simultaneity is two times higher than Walter＇sone. Utilizing the new architecture in modular exponentiation operation, we can reduce the latencies of nonsquare modular multiplication to half of that of [3]in the cost of one precomputation, and the lateneies of square modular are the same as in [3],in that the speed is faster, Of course, to keep balance between speed and hardware resource,we also provide methods to realize modular multiplication and exponentiation with n/2＋1 PEs, for which we have alsoprovided comprehensive analysis.

关 键 词：心动阵列 Montgomery模乘运算 模幂运算 Montgomery模乘算法 模乘运算 阵列结构 分割式 线性 WALTER WALTER 

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