问题标签 [montgomery-multiplication]

任何有 Xilinx Vivado HLS 和 FPGA 设计经验的人的疑问/问题：

我需要帮助减少在 HLS 范围内的设计利用率（即不能只重做 HDL 中的设计）。我的目标是 Zedboard (Zynq 7020)。

我正在尝试在 HLS 中实现 2048 位 RSA，使用 Tenca-koc 多字基数 2 蒙哥马利乘法算法，如下所示（更多算法细节here）：

我在 HLS 中编写了这个算法，它在模拟和 C/RTL cosim 中工作。我的算法在这里：

不幸的是，LUT 的利用率很高。

这是有问题的，因为我需要能够在硬件中安装多个这些块作为 axi4-lite 从站。

有人可以就如何在 HLS 范围内降低 LUT 利用率提供一些建议吗？

我已经尝试过以下方法：

• 尝试不同的字长
• 将顶级输入切换到数组，使其成为 BRAM（即不使用 ap_uint<2048>，而是使用 ap_uint foo[MWR2MM_e]）
• 尝试各种指令：划分为多个内联函数、数据流架构、lshr 的资源限制等。

但是，没有什么能真正以有意义的方式降低 LUT 利用率。是否有一种显而易见的方法可以降低对任何人来说显而易见的利用率？

特别是，我看过有关 mwr2mm 算法实现的论文（仅使用一个 DSP 块和一个 BRAM）。这甚至值得尝试使用 HLS 来实现吗？还是没有办法在不使用 HDL 描述的情况下实际控制算法映射到的资源？

谢谢您的帮助。

当在模幂运算算法中使用时，我对如何绕过radix-2 montgomery 模乘中的模的最终减法感到困惑。以下两篇论文提出了绕过减法的条件。

• 没有最终减法的蒙哥马利指数：改进的结果
• 蒙哥马利乘法不需要最后的减法

我不明白在“预处理和后处理”方面需要什么来消除在蒙哥马利乘法结束时重复减去模数的需要。

阅读上述论文后，我的理解是，要消除最后的减法，您必须：

1. 将每个输入操作数零扩展为模幂乘二

   /li>
2. 将蒙哥马利乘法内的循环边界增加 2，以便执行循环的另外两次迭代

我已经对工作算法进行了这些修改，但是结果与我预期的不一样，我不明白为什么。因此，我认为我误解了这些论文中的某些内容，或者遗漏了关键步骤。

让我们参考（类似 C 的伪代码）中的（工作）基数 2 蒙哥马利模幂函数。请注意，我已将操作数宽度扩展了两个最重要的零位（只是为了确保我没有溢出）。它们过去只有 2048 位。

我在报纸上遗漏了什么吗？我不认为这是一个实现错误，因为我的代码与论文中提出的完全一致。我相信我可能是一个概念错误。任何和所有的帮助表示赞赏。

谢谢！

我需要计算执行蒙哥马利乘法 页面 602-603与大小为 32 与 64 的字大小/寄存器之间的速度差异。

到目前为止，这是我的理解：

• x 和 y 由长度为 n 的多字数组表示，其中 n = m/w，w 是寄存器大小（32 或 64）。
• 蒙哥马利乘法的个位数乘法总数为 n*(2 + 2*n)，其中 n 表示字数组的数字长度。
• 我假设在每台计算机上两个个位数的乘法需要 1 个时钟周期。

如何将所有这些放在一起来表示具有 32 位寄存器或 64 位寄存器的计算机上的蒙哥马利乘法所需的时钟周期数？

我正在研究使用 montgomery 模乘法器的 RSA 算法实现，我不确定 2^2n 代表什么，是消息的 n 位数还是消息的 2^2n 位数，或者是什么别的。本 pdf 第 6 页：http: //www.journal.ftn.kg.ac.rs/Vol_11-1/11-Skobic-Dokic-Ivanovic.pdf

结果 C = P^e mod m
1. K= 2^2n mod m
2. Z= Monpro(1,K,M)
3. P= Monpro(P,K,m)
4. i=k-1 to i =0
一个。Z= Monpro(Z,Z,m)
b. 如果 ei = 1 那么 Z = Monpro(Z,P,m)
5. Z= Monpro(1,Z,m)
6. C=Z