Welcome to Rooeye's blog

蒙哥马利幂模运算 (快速幂取模算法)

OJ rooeye 1362℃ 0评论

若求 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:

  1. int RFS(int a,int b,int c)
  2. {
  3. if(b==1)
  4. {
  5. return a%c;
  6. }
  7. int temp = RFS(a,b>>1,c)%c;
  8. if(b%2==0)
  9. {
  10. return (temp*temp)%c;
  11. }
  12. return (a*(temp*temp))%c;
  13. }

递归版2:

  1. int Montgomery(int a,int b,int c)
  2. {
  3. if(b==0)
  4. {
  5. return 1;
  6. }
  7. int k = a%c;
  8. if((b&1)==0)
  9. {
  10. a = (k*k) %c;
  11. b = b>>1;
  12. return Montgomery(a,b,c);
  13. }
  14. return (k*Montgomery(a,--b,c))%c;
  15. }
非递归版:
  1. int function(int a, int b, int c)
  2. {
  3. int res = 1;
  4. a = a % c;
  5. while(b>0)
  6. {
  7. if(b % 2 == 1)
  8. res = (res * a) % c;
  9. a = (a * a) % c;
  10. b = b>>1;
  11. }
  12. return res;
  13. }

本算法的时间复杂度为O(logb)
来自为知笔记(Wiz)

转载请注明: Jinkun 的博客 » 蒙哥马利幂模运算 (快速幂取模算法)

喜欢 (0)
发表我的评论
取消评论

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址