快速模取幂算法及其证明

2019-04-14 08:54发布

站内文章 / 模拟电子
12660 0 1537

快速幂取模

求一个数的幂对另一个数的模的运算，称为模取幂。普通的计算方法很容易超出空间限制和时间限制。例如： 求a ^ b mod(n)， 利用模运算法则  (a*b)%n = (a%n)(b%n)%n，  可以大大提高计算的效率。 1：将b化为2进制，则由高位到低位为：Bn,B(n-1),……B1,B0.每一位Bi都只能是0或者1;  2： 因此a^b可以分解为( a^(2^n) )* (a^(2^(n-1) ) )……( a^2)*a;当然这个式子并不完全正确，只有当从右数的第k位B(k+1)为1的时候再要在式子中乘上一个( a^2^(k-1) ),如果为B(k+1) 0当然就不需要乘。 由该式，可以由a递推出所有的a^2^(k-1)； 3: a^(2^k)%c = ( (a^(2^(k-1))%c) * a^(2^(k-1)))  %c；
4:再把所有满足B(i)=1的a^(2^i)%c按照步骤3一样乘起来再%c就是结果， 即二进制扫描从最低位一直扫描到最高位；
LL mulmod( LL a, LL b , LL p ) { LL d =1; a = a%p; while( b>0 ) { if(b&1) d = (d*a)%p; a = (a*a)%p; b>>=1; } return d; }在这段代码中 ，a在递归的推导a^(2^k)%c。d则将目前求出的a^(2^k)%c和之前的累积求积再取模。 本代码和思路都参考他人的博客。仅代表记录学习过程。

热门文章