【算法分析】——快速幂算法

做一个柔情的程序猿 2020-12-13

412

点击箭头处“蓝色字”，关注我们哦！！

算法

快速幂算法

● ○ ●

Fast Power Algorithm

● ○ ●

设a,b,c都是正整数，计算a的b次方对c取模（a ^ b % c）
在非对称密钥算法RSA中是一个很基本的问题，由于a,b,c
可能会比较大，直接计算显然无法满足效率要求，可以借鉴快速幂的思想减少计算次数。

做法是根据b的奇偶性，分情况讨论：

❉❉❉❉❉❉❉❉❉❉

b为偶数

如果b为偶数
，不妨设b = 2k
，那么

a ^ b % c  
= a ^ 2k % c  
= (a ^ k % c) * (a ^ k % c) % c  
= (a ^ k % c) ^ 2 % c

b为奇数

如果b为奇数
，不妨设b = 2k + 1
，那么

a ^ b % c  
= (a * a ^ 2k) % c  
= (a % c) * (a ^ 2k % c) % c  
= (a % c) * ((a ^ k % c) ^ 2 % c) % c

可见，无论奇偶，计算规模都可以缩至原来的一半，时间复杂度由O(b)降至O(logb)
。

根据以上递推式，很容易写出解决该问题的递归算法。

int powmod(int a, int b, int c) {
    if (0 == b) return 1;
    long long x = powmod(a, b/2, c);
    x = x * x % c;
    if (b & 1) x = x * a % c;
    return x;
}

如果将实现改成迭代方式就是这样：

int powmod(int a, int b, int c) {
    long long x = 1, t = a;
    while (b) {
        if (b & 1) x = x * t % c;
        t = t * t % c;
        b = 2;
    }
    return x;
}