幂后取模算法

Question

下面一段代码计算a^b%c的值，

int powermod(int a,int b,int c)
{
    int ans = 1;
    while(b)
    {
        if(b&1)
            ans=(ans*a)%c;

        a=(a*a)%c;
        b=b>>1;
    }
    return ans;
}

我试图理解代码背后的算法，但无法理解。有人可以帮我解释一下吗？这是如何工作的，它背后的算法有名字吗？

Answer 1

如果没有 "modulo c" 部分，则更容易看到发生了什么：

int power(int a,int b)
{
    int ans = 1;
    while(b)
    {
        if(b&1)
            ans *= a;
        a=a*a;
        b=b>>1;
    }
    return ans;
}

这是计算 a^b 的标准算法，一次考虑 b 一位，从最低有效位开始。对于b的每一位，如果是1，则将答案乘以a的当前值。然后，要移动到下一位，对 a 进行平方并将 b 向右移动 1 位。该算法的理论是 x^{2^m + 2ⁿ} = x^{2^m}x^2ⁿ.

这种算法称为 "exponentiation by squaring"、"square-and-multiply" 或 "binary exponentiation"。

发布的算法（在评论中指出的更正后）做同样的事情模 c，使用 (x*y)%z == ((x%z) * (y%z)) % z 的事实（也就是说，模运算可以在之前或之前应用乘法）。它使用它来保持 a 小于 c 尽管重复平方。

Answer 2

使用二元思维

a^b = a^b1 a^b2 ... a^bn 当 b1+...+bn=b

将b写成二进制，得到a^b0 a^2*b1 a^4*b2 ... a^2ⁿbn ,bi表示二进制b中的第i位。只能是0或1。

现在我们发现不需要每次都计算a^2ⁿ，因为我们可以从a ^{2^n-1}

因为(ab)%c=(a%c)(b%c)%c，这个算法在乘法时做mod操作。

幂后取模算法

Algorithm of calculate modulo after power

c++

algorithm