邬贵明，谢向辉，吴 东，郑 方，严忻恺

(数学工程与先进计算国家重点实验室， 江苏 无锡 214125)

高基Montgomery模乘阵列结构设计与实现*

邬贵明，谢向辉，吴 东，郑 方，严忻恺

(数学工程与先进计算国家重点实验室， 江苏 无锡 214125)

提出了两种高基Montgomery模乘线性阵列结构。两种线性阵列结构分别利用两种不同的并行化开发方法，沿不同的循环维度进行任务分配和调度，都能够充分开发算法的流水线并行。在Xilinx XC5VLX330 FPGA上实现了两种256位宽、基为216的模乘阵列结构。实验结果表明，两种结构具有84个时钟周期的延迟，吞吐率分别为1/17和1/21，与相关结构相比吞吐率更高。两种结构在性能和实现代价间能够达到合理平衡。

模乘；线性阵列结构；现场可编程阵列；流水化

1 引言

最常用的模乘算法是Montgomery模乘算法[1]，在软件实现和硬件实现两方面都非常高效。它使用简单的移位操作来代替更费时的除法操作，使用部分结果加模数倍数的方法来代替部分结果减模数倍数的方法，其好处是加法操作在被乘数的最低位处理后就可以立即开始，不用等到所有位处理完再开始，这一特性有利于开发并行性。

目前，学术界提出了大量Montgomery模乘硬件加速结构，这些结构可分为以下几类：基2模乘结构、多字基2模乘结构、高基模乘结构和采用大整数乘法器的模乘结构。1999年Tenca A F和 Koç Ç K[2]首次提出一种多字基2的Montgomery乘法算法和硬件实现，当操作数为n位时，一次Montgomery模乘需要2n个时钟周期。为降低计算延迟，大量研究人员基于Tenca A F和Koç Ç K的工作进行改进，其中Huang M[3]的工作最为突出，利用最高位的两种可能性预先对部分结果进行计算，将一次Montgomery模乘运行时间降为n个时钟周期，性能提升了1倍。……