大数取模运算,快速幂取模运算

2019-04-14 12:42发布

1.快速幂取模

http://www.cnblogs.com/yinger/archive/2011/06/08/2075043.html 快速幂取模就是在O(logn)内求出a^n mod b的值。算法的原理是ab mod c=(a mod c)(b mod c)mod c  long exp_mod(long a,long n,long b) { long t; if(n==0) return 1%b; if(n==1) return a%b; t=exp_mod(a,n/2,b); t=t*t%b; if((n&1)==1) t=t*a%b; return t; }

2.大数取模运算Barrett reduction

https://blog.csdn.net/ykry35/article/details/79179285 Barrett reduction算法的证明和使用。 作者刚做完了课程设计作业,闲来无事写篇文章。 大数中的指数运算,需要对一个数进行取模,因为最大可能二进制下2048位的2048位次方,所以必须边做乘法边取模。 乘法使用快速幂,如果底数位数是x,指数位数是e,底数足够大的话,复杂度取决于模数,模数是m位的话,复杂度是O(m*m*e)。程序里,大数的存储是2的32次方进制的,这里的m*m要除以(32*32)。 取模运算,如果直接调用大数取模,因为除法是很慢的,所以效率很低。用Barrett reduction算法可以将除法转化为乘法和位运算,减法。 因为模数是任意的,所以不用蒙哥马利算法。 作业里只要求完成非负的大数运算,后面证明中默认大数都是非负的。 下面介绍Barrett reduction算法 求 x mod m  m的位数是k 使用条件: x位数不大于2*k。对同一个数反复取模。 使用方法(这里是非负数): 计算常量 mu=b^2k / m 取模时: q1 = x / b^(k-1) q2 = q1 * mu q3 = q2 / b^(k+1) r1 = x % b^(k+1) r2 = (q3 * m) % b^(k+1) r = r1 - r2 if ( r > m ) r -= m return r 很多资料把mu=b^2k / m写成了mu=b^k / m,作者被坑了,很生气,决定放假写这么一个文章。另外,百度上基本看不到什么相关的证明。 证明:  []表示取整,b是大数的进制   只需要一次除法预处理。 之后的除法和取模都是对进制b的若干次方进行的,所以位运算即可。 乘法时,因为最后结果是要取最后k+1位的,所以在乘的时候,可以直接把k+1位前面的丢弃,减少循环次数。作者是另外写了一个限制位数的乘法函数,效率提升了一些。 证明部分截图自word实验报告。    

大数取模:一般取模+技巧取模+快速幂取模+欧拉函数(费马小定理)

https://blog.csdn.net/u011361880/article/details/77802742 一般取模运算(不推荐): 
(a^n)%m。 我们可以改写为(a^n)%m= ((a%m)^n)%m, 即循环n次。 
缺点:低效,循环了n次。 int exp_mod(int a,int n,int m){ a = a%m; int temp = 1; while(n--) { temp = temp * a; temp = temp % m; } return temp; }   第一种,技巧取模: 
(a^n)%10 
当n非常大时,嗯,只能用字符串存n的时候。 简单分析一下, 
a%10. 有10种可能,(来源于室友“张博士”的逆天发现,明明可以靠脸吃饭,他偏偏要靠才华,明明可以快速幂取模,它偏要发现这种,出现大大大大数的) a%10 = 0. 这个结果就不需要看了。0 
a%10 = 1. (1^n )%10会出现的可能数字:1 
a%10 = 2. (2^n )%10会出现的可能数字:2,4(=2*2), 8(=2*4),6(=2*8),继续循环,2, 4, 8, 6….. a%10 = 3. (3^n )%10会出现的可能数字:3,9(=3*3),7(=3*9), 1(=3*7),继续循环,3,9,7,1….. a%10 = 4. (4^n )%10会出现的可能数字:4,6(4*4) , 继续循环,4,6…… a%10 = 5. (5^n )%10会出现的可能数字:5 
a%10 = 6. (6^n )%10会出现的可能数字:6 
a%10 = 7. (7^n )%10会出现的可能数字:7, 9, 3, 1 继续循环, 
a%10 = 8. (8^n )%10会出现的可能数字:8, 4, 2, 6 继续循环, 
a%10 = 9. (9^n )%10会出现的可能数字:9, 1 继续循环, 重点是继续循环,发现,最大情况下,都是以4位数字循环,换句话说,(a^n)%10 和(a^(n+4))%10是相等的,当然,这里n不等于0. 如果这里看懂了,那这里差不多就ok了。 我们把n –> (n%4)+4. 这里加4的原因是为了防止n%4==0. ,并且我们没有考虑n==0的情况。这个单独处理一下。 OK 
如果n != 0. 
(a^n)%10 = (a^(n%4+4))%10 = ((a%10)^(n%4+4)) % 10 另外友情提示:对于n,如果是字符串存储,(十进制) 我们只需要取最后的2位数,用它代替n即可,因为999, 900肯定是可以被4整除的,我们只需要99即可,用99%4+4。 
如果是int 型或longlong。(二进制) (n & 11)按位“与”可以取出后2位,代替n%4,(注意不能代替n%4+4 . 加4一直需要),第3位是4,肯定可以被4整除。 第二种,快速幂取模: 
从一般取模的代码中,我们可以发现,每次都是重复的乘a。那么能否考虑,翻倍呢。看下面代码, 
这部分代码来源于 
http://www.cnblogs.com/yinger/archive/2011/06/08/2075043.html 
简单分析一下,类似于折半查找。 (a^n) %b long exp_mod(long a,long n,long b) { long t; if(n==0) return 1%b; if(n==1) return a%b; t=exp_mod(a,n/2,b); t=t*t%b; if((n&1)==1) t=t*a%b; return t; }   这个代码就是一般的折半,递归,折半….。注意,(n&1) 按位“与 ”,如果是奇数,那么结果是1,否则结果是0. 来个惊喜一点的代码: 
来源于大神的回复 
http://www.cnblogs.com/yinger/archive/2011/06/08/2075043.html (a^n) %b int exp_mod(int a,int b,int n){ int r=1; while(b){ if(b&1)r=(r*a)%n; a=(a*a)%n; b>>=1; // b = b>>1; } return r; }   主要思想还是折半。但是运用的非常巧妙,假设b是一个偶数,并且b/2.b/4,b/8.。。。。一直到2都是偶数, OK,假设b == 16. a==2. 
b = 16,8,4,2,1 
我们发现,只有最后一次,b==1,时,我们进入了if语句, 
我们查看while循环里面,a的变化。(这里先不考虑模) 
b=16,进入while a = 2^2; 
b=8, a = 2^4; 
b=4, a = 2^8; 
b=2, a = 2^16 
b=1, ,进入if语句,r = a, 此时返回的是r。 假设b=18. 
b=18,进入while a = 2^2; 
b=9, 此时,进入了if语句。r=2^2. a = 2^4; 
b=4, a = 2^8; 
b=2, a = 2^16 
b=1, ,进入if语句,r = r*a = 2^2 * 2^16 , 此时返回的是r。 我们发现,在b=9时,我们用r保存了2^2. 为什么呢。反过来,从下往上看,我们要计算2^18次方。但是我们此时只知道2^8的结果,我们并不知道2^9是多少。因此,我们用了2个2^8. 此时,我们还是差了一个2^2. 
r保存的刚好是这个值。 当b是奇数时。b越小,说明离18越远,从下往上乘,我们一开始是差一个2(b=8和b=9差一个2),一直往上翻倍,即到了18,差2个2.即2^2。因此,r的值也需要越来越大。 (这里需要好好理解。) 
每碰到一次奇数,我们都会和原来的差一个2. 然后这个奇数距离18的距离越远。我们需要补回去的值就越大,即r的值。 重新举一个例子: 
b=22 进入while a = 2^2 
b=11 进入if,r = 2^2. a=2^4 ——>要补回2^2 
b=5 进入if, r=2^2 * 2^4. a = 2^8 ——> 要补回2^4 
b=2 a=2^16 
b=1,进入if, r = 2^2 * 2^4 * 2^16 
当b=11时,只知道2^5,用了两个,可以变成2^10. 
和11相差一个2.再到22即相差两个2. 
当b=5时,只知道2^2.用了两个。可以变成2^4,相差一个2. 再到10(11)时,翻倍,变成了2个。 
(10到11,在b=11那里已经补回来了),再到22,翻倍,变成2个。 第三种,欧拉函数: 
先介绍一个定义,互质:a和b互质,即a和b除了1以为,没有其他公约数。 
对正整数n,欧拉函数是小于n的数中与n 互质的数的数目, 
φ(8)=4,因为1,3,5,7均和8互质。 费马小定理: 
对于互质的整数a和n,有a^φ(n) ≡ 1 mod n 
即(a^φ(n)) % n = 1 %n = 1; 我们常常会见到。求(a^n)%1000000007, n>1000000007. 
因为m=1000000007是质数,毫无疑问,φ(m) = m-1 = 1000000006. 假设n = k * 1000000006 +r .其中r是余数, 
我们利用费马小定理降级处理。 (a^n)%1000000007 = (a^( k * 1000000006 +r ))%1000000007 
=(a^( k * 1000000006 ))%1000000007 * (a^r )%1000000007 
=1 * (a^r )%1000000007 直接把n变成了r。