Montgomery乘法-32位寄存器与64位寄存器

Question

我需要计算使用大小为32与64的字大小/寄存器执行Montgomery乘法第602-603页之间的速度差。

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

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

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

Answer 1

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

使用内存访问重写算法(假设乘法可以与加载/存储并行进行)：

1. 对于从0到n:a_i <- 0的i
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. 对于从0到(n-1)的CCD_ 13：
      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. 如果是CCD_ 22，则是A <- A − m
4. 返回(A)

希望这能有所帮助。