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。