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

Question

我需要计算执行蒙哥马利乘法 页面 602-603与大小为 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 位寄存器 (x y R^-1 mod m) 只需要 192 个寄存器来存储操作数 (3*(1024/32))。实际上，您需要考虑内存访问才能回答这个问题。

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

1. 对于i从 0 到 n：a_i <- 0
2. 对于i从 0 到 (n − 1)，请执行以下操作：
   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. 返回（A）。

希望这可以帮助。