algorithm - 当 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. 最坏的情况是 2k 指数乘法 (2^k)-1

有关详细信息，请参阅相关的QA:

• Power by squaring for negative exponents
• modular arithmetics and NTT (finite field DFT) optimizations