快速幂取模

115 阅读 0 评论 76 点赞

我是靠谱客的博主大意奇异果，这篇文章主要介绍快速幂取模，现在分享给大家，希望可以做个参考。

问题定义：

数论中经常出现的一个问题是对一个数的幂取模，也称为模取幂，即求a^b mod n。如果计算量较小，可以直接计算出a^b的值，再作模n运算。但是如果a和b的值都非常大，a^b的值用计算机难以表示，或者即使可以用大数运算的方式用计算机表示，也会因为耗时过长难以应用。基于模运算的基本性质，可以设计出一种算法，快速求解这一问题。这种方法为“快速幂取模”，也称为“反复平方法“。

算法原理：

算法基础在于模运算的基本性质
(a+(*)b)%n=(a%n+(*)b%n)%n
(a-b)%n=(a%n-b%n+n)%n
(a*b)%n=(a%n*b%n)%n

算法实现的原理是：

算法1：利用公式a*b%c=((a%c)*b)%c,这样每一步都进行这种处理，这就解决了a^b可能太大存不下的问题，但这个算法的时间复杂度依然没有得到优化
代码如下：

复制代码

1
2
3
4
5
6
7
8
9
10
int modexp_simple(int a,int b,int n)
{
int ret = 1;
while (b--)
{
ret = a * ret % n;
}
return ret;
}

算法2：另一种算法利用了二分的思想，可以达到O(logn)。
可以把b按二进制展开为：b = p(n)*2^n + p(n-1)*2^(n-1) +…+ p(1)*2 + p(0)
其中p(i) (0<=i<=n)为 0 或 1

这样 a^b = a^ (p(n)*2^n + p(n-1)*2^(n-1) +…+ p(1)*2 + p(0))
= a^(p(n)2^n) a^(p(n-1)2^(n-1)) …* a^(p(1)2) a^p(0)
对于p(i)=0的情况, a^（p(i) * 2^(i-1) ） = a^0 = 1,不用处理
我们要考虑的仅仅是p(i)=1的情况
化简：a^(2^i) = a^(2^(i-1) * 2) = ( a^( p(i) * 2^(i-1) ) )^2
（这里很重要！！具体请参阅秦九韶算法：http://baike.baidu.com/view/1431260.htm）
利用这一点，我们可以递推地算出所有的a^(2^i)
当然由算法1的结论，我们加上取模运算：
a^(2^i)%c = ( (a^(2^(i-1))%c) * a^(2^(i-1))) %c
于是再把所有满足p(i)=1的a^(2^i)%c按照算法1乘起来再%c就是结果，即二进制扫描从最高位一直扫描到最低位

实例代码：递归

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//计算a^bmodn
int modexp_recursion(int a,int b,int n)
{
int t = 1;
if (b == 0)
return 1;
if (b == 1)
return a%n;
t = modexp_recursion(a, b>>1, n);
t = t*t % n;
if (b&0x1)
{
t = t*a % n;
}
return t;
}

实例代码2：非递归优化

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>

using namespace std;
//计算a^bmodn

int modexp(int a,int b,int n)
{
int ret=1;
int tmp=a;
while(b)
{
//基数存在

if(b&0x1) ret=ret*tmp%n;
tmp=tmp*tmp%n;
b>>=1;
}
return ret;
}
int main()
{
cout<<modexp(2,10,3)<<endl;
return 0;
}