这个问题源于我几乎写在这个问题下面的评论，其中 Zack 正在计算大量模数的阶乘（为了这个问题，我们将假设它是素数）。Zack 使用传统的阶乘计算，在每次乘法时取余数。

我几乎评论说要考虑的替代方案是Montgomery multiplication，但仔细想想，我只看到这种技术用于加速同一个被乘数的多次乘法（特别是加快ⁿ mod p 的计算）。

我的问题是：蒙哥马利乘法可以用来加速n的计算！大 n 和 p 的 mod p？

我在 Verilog 中的结构建模方面有一些相当不错的经验，但我对其他建模方法几乎没有任何经验。所以，请帮帮我。代码编译得很好，但是在模拟时它只是挂起。什么都没发生。如果它很重要，则代码是蒙哥马利模乘法器。这比我的学术水平高一点，但我已经设法理解了算法并编写了代码。为什么模拟不运行？提前非常感谢！

我有 N 个 1024 位。我需要将消息 M（512 位）转换为蒙哥马利简化形式，如下所示。

M' = M * R^{-1} mod N

其中 , R = 2 ^ 512 (mod N)

我怎样才能达到结果？

蒙哥马利乘法如何加速计算 RSA 加密中使用的 c=m^e%n 的加密过程？我知道蒙哥马利乘法可以有效地将 a*b%n 相乘，但是当试图找到 m^e%n 时，有没有比每次循环并计算蒙哥马利乘法更有效的方法来将 m*me 相乘？

我正在使用 gmp 库，所以我可以在这里处理更大的数字。r 和 r_p 在单独的函数中预先计算并且是全局的。在这个例子中，我正在使用 10 的幂（尽管我意识到使用 2 的幂会更有效）

我在乘法之前转换为蒙哥马利形式，并在 for 循环中重复乘法 m*m，在 m^e 步骤结束时转换回正常世界。我很想知道是否有另一种方法可以以不同的方式计算操作 m^e%n，而不仅仅是在 for 循环中循环？截至目前，我相信这是计算的瓶颈，但我很可能是错的。

实际的蒙哥马利乘法步骤发生在下面的函数中。

这就是 RSA 加密如何与蒙哥马利乘法优化一起工作的吗？

我正在用 JavaCard 开发软件以添加 ECC 中的点。问题是我需要一些基本操作，所以目前，我需要乘法和求逆，我已经有了加法和减法。

我试图开发蒙哥马利乘法，但它适用于 GF(2^m) （我认为）。

所以我的例子是：

例如 A = 2, B =3, p= 3 C 必须是 0, C = A. B (mode p) 但是这个例子 A = 7, B=2, p=5 , C 必须是 4，但我有49.

有人可以帮我吗？

更多方法：

目前我试图简单，但想法是乘以非常大的数字，如字节数组[10]

我正在硬件（xilinx ZYNQ FPGA）中实现 RSA 1024，但无法找出一些奇怪的问题。最值得注意的是，我发现我的实现仅适用于某些基数/指数/模数组合，但没有找到任何原因。

注意：我正在使用 Xilinx HLS（本质上是合成到硬件中的 C 代码）来实现该算法。为了这篇文章，把它当作一个标准的 C 实现，除了我可以有高达 4096 位宽的变量。我还没有并行化它，所以它的行为应该就像标准 C 代码一样。

问题

我的问题是我能够得到某些模幂测试问题的正确答案，但前提是基数、指数和模数的值可以写成比实际的 1024 位操作数宽度少得多的位（即它们是零填充）。

当我使用从 SSH-keygen 生成的实际 1024 位值时，我不再得到正确的结果。

例如，如果我的输入参数是

我正确地得到了1570^1029 mod(3337) = 688的结果

但是，当我实际使用占据所有（或大约所有）1024 位的值作为输入时......

我错误地得到一个大数字，而不是 29 (0x1D) 的正确答案

我已经检查了这两种算法一百万次，并尝试了不同的初始值和循环边界，但似乎没有任何效果。

我的实现

我使用标准的平方和乘法进行模幂运算，我选择使用 Tenca-Koc radix-2 算法进行蒙哥马利乘法，在下面的伪代码中详细说明...

我的蒙哥马利乘法实现如下：

}

我的顶级模幂运算如下，其中（切换符号！）...

我一生都无法弄清楚为什么这适用于除了实际的 1024 位值之外的所有内容。任何帮助将非常感激

我需要在我的应用程序中执行快速的伽罗瓦域算术。我有一个用汇编语言编写的乘法函数，该函数已针对我的平台 MSP430 微控制器进行了优化。该函数计算两个任意大小的大数的乘积，但每个数字必须表示为一个 16 位整数数组。但是，在我的项目中，伽罗瓦域元素表示为 16 个 64 位整数的数组。如何将我的 16 个 64 位整数数组转换为优化的、基于汇编的乘法函数所需的表示（即 64 个 16 位整数数组）？当然，简单地将数组转换为 (UInt16 *) 是行不通的。

MSP430 是一种小端架构。在此先感谢您的任何建议。

我设计了一个 16*16 的蒙哥马利乘法器。该代码使用一个 16*16 乘法器来执行三个乘法。使用相同的乘法器一个接一个地执行乘法，并且每次乘法的结果存储在寄存器中。单个 16*16 乘法器的执行频率约为 1550 MHz，但当三个乘法器串联执行时，Montgomery 乘法器（使用单个 16*16 乘法器 3 次）的频率降低到几乎 500 MHz。我想避免频率降低，并希望以单倍频器的频率对其进行操作。在这方面需要帮助。

提供了代码。（在这种情况下仅提供乘法。为简单起见，已排除加法，移位）

我在 Python 3.x 上尝试蒙哥马利乘法算法。该算法伪代码如下：

编写的 Python 3.x 代码如下：

但是，代码没有给出正确的结果。问题是什么？

谢谢回答。

背景

我正在尝试使用各种不同的蒙哥马利方法在硬件（xilinx ZYNQ FPGA）中实现 RSA 2048。我正在使用 Xilinx HLS（本质上是合成到硬件中的 C++ 代码）来实现该算法。

注意：为了这篇文章，把它当作一个标准的 C++ 实现，除了我可以有像位向量一样的变量，最多 4096 位宽，并使用foo[bit]orfoo.range(7,0)语法访问各个位。我还没有并行化它，所以它的行为应该和标准 C++ 代码一样。请不要害怕并停止阅读，因为我说的是 FPGA 和 HLS 这个词。只需将其视为 C++ 代码即可。

我已经能够得到一个工作原型，它使用标准的平方乘法进行模幂运算，使用标准的 radix-2 MM 算法进行模乘运算，但是它在 FPGA 上占用了太多空间，我需要使用较少的资源密集型算法。

为了节省空间，我正在尝试实现此处提出的Tenka-koc Scalable Multiple Word Radix 2 Montgomery Multiplication (MWR2MM)。我已经为此苦苦挣扎了一个月，但无济于事。然而，由于我的挣扎，我无法弄清楚一个有趣的问题。

问题

我的问题是 MWR2MM 在执行蒙哥马利乘法时没有返回正确的答案。但是，我开始认为这不是编码错误，而是我只是误解了有关算法使用的关键内容。

MWR2MM 算法有多种变体，实现方式大相径庭，我已经尝试实现其中的许多。我目前有 4 种不同的 MWR2MM 实现编码，所有这些都基于对许多论文中提出的算法的修改。是什么让我认为我的实现实际上是正确的，因为所有这些不同版本的算法都返回相同的错误答案！我不认为这是巧合，但我也不认为已发布的算法是错误的......因此，我认为实际上正在发生更邪恶的事情，并且我的算法实现是正确的。

示例 1

例如，以tenca-koc的论文中提出的原始MWR2MM为例，我们将其称为MWR2MM_CSA，因为该算法的加法运算在硬件实现时都使用了进位保存加法器（CSA）。

• S 是部分和
• M 是模数
• Y 是被乘数
• X 是乘数，x_i（下标）是单个位（例如 X = (x_n,...,x_1,x_0)。
• 上标是词向量（例如 M = (0,M^{e-1},...,M^1,M^0)
• (A,B) 是两个位向量的串联。
• m 是操作数的宽度
• w 是所选单词的宽度
• e 是完成向量所需的 w 位字数，（例如 e = ceil((m+1)/w) ）

我对该算法的实现使用以下参数：

• MWR2MM_m = 2048 (operand size, m from above)
• MWR2MM_w = 8 (word size, w from above)
• MWR2MM_e = ceil( (e+1)/w ) = 257 (number of words + 1 per operand, e from above)
• ap_uint<NUM_BITS>是如何在 HLS 中声明位向量

我的代码：

现在，我的理解是（引用上面的论文）

两个整数 X 和 Y 的蒙哥马利乘法 (MM) 算法，具有 n 位精度所需的参数，将产生数字 MM(X,Y,M) = X Y (2^-n) (模 m)，其中 r=2^n 且 M 是 (2^(n-1), 2^(n)) 范围内的整数，使得 gcd(r,M)=1。由于 r=2^n ，模数 M 为奇数就足够了。

因此，我们应该期待以下结果（通过软件库验证）：

但是相反，我的算法返回

示例 2

好的，所以也许那个实现是错误的。让我们尝试另一个修改版本，MWR2MM_CPA 算法（以硬件中使用的进位传播加法器命名）：

还有我对 MWR2MM_CSA 的实现：

}

当使用相同的 X、Y 和 M 运行时，这也返回与 MWR2MM_CSA 完全相同的错误结果，尽管位级操作不同。

为简洁起见，我将省略其他两种也返回相同错误结果的算法。我应该注意到，当使用 4 位操作数大小和 2 位字大小时，这两种算法都能正常工作。然而，任何其他操作数大小/字长组合都是不正确的，但对于所有四种不同的位级实现具有相同的不正确结果。

我一生都无法弄清楚为什么所有四种算法都返回相同的错误结果。我在第一个示例中的代码逐字逐句地与tenca-koc 论文中提出的算法完全相同！

假设 MWR2MM 算法应该返回与标准 radix-2 MM 算法相同的结果（在蒙哥马利域中），我是否不正确？它们具有相同的基数，因此无论字长如何，结果都应该相同。我应该不能相互交换这些算法吗？

很抱歉这篇冗长的帖子，但我想非常准确和连贯地解释问题所在。我不是在寻求帮助调试我的代码，而是试图弄清楚我是否误解了蒙哥马利乘法算法的基本特征。也很好奇为什么不同的实现会给出相同的错误结果。

谢谢！