当 d 是 k 位指数时，使用平方乘法算法计算 m^d mod n 所需的最大乘法次数是多少?

Question

哪个指数 d 将 需要这么多？

非常感谢有关如何解决此问题的任何建议。

Answer 1

假设无符号整数和简单幂，通过平方算法，如下所示：

DWORD powuu(DWORD a,DWORD b)
{   
int i,bits=32;
DWORD d=1;
for (i=0;i<bits;i++)
{
d*=d;
if (DWORD(b&0x80000000)) d*=a;
b<<=1;
}
return d;
}

您只需将a*b替换为modmul(a,b,n)或(a*b)%n，因此答案是：

1. 如果指数有k位并且设置了l，则需要k+l乘法
2. 最坏的情况是指数(2^k)-1的2k乘法

有关更多信息，请参阅相关的QA：

• 负指数的平方幂
• 模块化算法和NTT(有限场DFT)优化

Answer 2

对于朴素的实现，它显然是具有最大汉明权重(设置位数)的指数。在这种情况下(2^k - 1)需要最多的乘法步骤：(k)。

对于 k 元窗口方法，乘法次数可以独立于指数。 例如，对于固定的窗口大小：w = 3我们可以计算{m^0, m^1, m^2, m^3, .., m^7}组系数(在这种情况下都是mod n，并且可能以蒙哥马利表示有效约简)。结果是ceil(k/w)乘法。这在加密实现中通常是首选，因为指数不会通过简单的定时攻击来显示。任何 k 位指数都具有相同的时序。(如果假设攻击者对缓存性能等具有"细粒度"访问权限，则实际情况会稍微复杂一些。

滑动窗口技术通常更有效，并且仅比固定窗口方法更难实现。 但是，它们也会泄漏侧信道数据，因为时序将取决于指数。此外，众所周知，要使用的"最佳"序列是一个难题。