蒙哥马利乘法 - 32 位寄存器与 64 位寄存器

Question

我需要计算执行 Montgomery Multiplication 第 602-603 页 与 word-size/register 大小 32 与 64 之间的速度差异。

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

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

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

Answer 1

如果所有中间单精度乘法操作数和结果在寄存器中可用，则多精度蒙哥马利乘法的周期数确实是 n(2+2*n)。对于加密操作，这几乎是不可能的，因为 m 通常是 1024 或更大。假设 32 位寄存器 (xyR^-1 mod m) 只需要 192 个寄存器来存储操作数 (3*(1024/32))。事实上，您需要考虑内存访问才能回答这个问题。

使用内存访问重写算法（假设乘法可以与 loads/stores 并行完成）：

1. 对于 i 从 0 到 n: a_i <- 0
2. 对于从 0 到 (n − 1) 的 i，请执行以下操作：
   1. 获取a_0
   2. 获取y_0
   3. 获取x_i
   4. 计算u_i <- (a_0 + x_i*y_0)m' mod b。将 u_i 存储在寄存器中
   5. c = 0（计算A <- (A + x_i*y + u_i*m)/b）
   6. 对于 j 从 0 到 (n-1)：
      1. 获取a_j
      2. 获取y_j
      3. 计算 (cv) = a_j + x_i*y_j + c，获取 m_j
      4. 计算(cv) = (cv) + u_i*m_j，如果j>0存储a_{j-1} <- v
   7. 存储a_n <- c和a_{n-1} <- v
3. 如果A >= m那么A <- A − m。
4. Return(A).

希望这对您有所帮助。