蒙哥马利幂模运算 (快速幂取模算法)
若求 a^b mod c：
1.如果b是偶数， a^b mod c = (（(a^2) mod c ）^(b/2) ) mod c
2.如果b是奇数， a^b mod c = (（(a^2) mod c ）^(b/2) *a) mod c
如果要求 a^b mod c , 假设 a = 3，b = 18 , mod =14:
3 ^ 18 mod 14
= (3 ^ 9) ^2 mod 14
= ( ( (3 ^ 9) mod 14 ) ^ 2 ) mod 14 //3 ^ 18 mod 14 问题转化为(3 ^ 9) mod 14，复杂度减小一半
(3 ^ 9) mod 14
= ( ( ( 3 ^ 4 ) ^2 ) mod 14 *3 ) mod 14
= ( ( ( 3 ^ 4 ) mod 14 ) ^ 2 * 3) mod 14 //(3 ^ 8) mod 14 问题转化为( 3 ^ 4 ) mod 14，复杂度减小一半
( 3 ^ 4 ) mod 14
= ( 3 ^ 2 ) ^2 mod 14
= ( ( ( 3 ^ 2 ) mod 14 ) ^ 2 ) mod 14 //(3 ^ 4) mod 14 问题转化为( 3 ^ 2 ) mod 14，复杂度减小一半
( 3 ^ 2 ) mod 14
= ( 3 ^1 ) ^2 mod 14
= ( ( ( 3 ^ 1 ) mod 14 ) ^ 2 ) mod 14 //(3 ^ 2) mod 14 问题转化为( 3 ^ 1 ) mod 14，复杂度减小一半
这样复杂度就变为了 O(logb),对于任何数字，循环迭代上述过程得到最终结果。
快速幂算法：
递归版1：
int RFS(int a,int b,int c){if(b==1){return a%c;}int temp = RFS(a,b>>1,c)%c;if(b%2==0){return (temp*temp)%c;}return (a*(temp*temp))%c;}
递归版2：
int Montgomery(int a,int b,int c){if(b==0){return 1;}int k = a%c;if((b&1)==0){a = (k*k) %c;b = b>>1;return Montgomery(a,b,c);}return (k*Montgomery(a,--b,c))%c;}
非递归版：
int function(int a, int b, int c){int res = 1;a = a % c;while(b>0){if(b % 2 == 1)res = (res * a) % c;a = (a * a) % c;b = b>>1;}return res;}
本算法的时间复杂度为O（logb）