模幂运算

2019-04-13 14:44发布

概念:
  模运算即求余运算。“模”是“Mod”的音译,模运算多应用于程序编写中。 Mod的含义为求余。模运算在数论和程序设计中都有着广泛的应用,从奇偶数的判别到素数的判别,从模幂运算到最大公约数的求法,从孙子问题到凯撒密码问题,无不充斥着模运算的身影。虽然很多数论教材上对模运算都有一定的介绍,但多数都是以纯理论为主,对于模运算在程序设计中的应用涉及不多。
  模幂运算则是指先进行幂运算,在进行模运算。 算法:
1)描述:
  根据运算规则ab % p = ((a % p)b) % p ,我们知道3333^5555(%10)= 3^5555(%10)。由于3^4 = 81,所以3^4(%10)= 1。
  根据运算规则(3) (a * b) % p = (a % p * b % p) % p ,由于5555 = 4 * 1388 + 3,我们得到3^5555(%10)=(3^(4*1388) * 3^3)(%10)=((3^(4*1388)(%10)* 3^3(%10))(%10)=(1 * 7)(%10)= 7。
  计算完毕。
  利用这些规则我们可以有效地计算X^N(% P)。简单的算法是将result初始化为1,然后重复将result乘以X,每次乘法之后应用%运算符(这样使得result的值变小,以免溢出),执行N次相乘后,result就是我们要找的答案。
  这样对于较小的N值来说,实现是合理的,但是当N的值很大时,需要计算很长时间,是不切实际的。下面的结论可以得到一种更好的算法。
  如果N是偶数,那么X^N =(X*X)^[N/2];
  如果N是奇数,那么X^N = X*X^(N-1) = X *(X*X)^[N/2];
  其中[N]是指小于或等于N的最大整数。  2)源码:
1 // 函数功能:利用模运算规则,采用递归方式,计算X^N(% P) 2 // 函数名:PowerMod 3 // 输入值:unsigned int x,底数x 4 // unsigned int n,指数n 5 // unsigned int p,模p 6 // 返回值:unsigned int,X^N(% P)的结果 7 unsigned int PowerMod(unsigned int x, unsigned int n, unsigned int p) 8 { 9 if (n ==0) 10 { 11 return1; 12 } 13 unsigned int temp = PowerMod((x * x)%p, n/2, p); //递归计算(X*X)^[N/2] 14 if ((n &1) !=0) //判断n的奇偶性 15 { 16 temp = (temp * x) % p; 17 } 18 return temp; 19 }
转载自:http://www.cnblogs.com/ziwuge/archive/2011/09/18/2180480.html