模取幂运算

2019-04-13 14:24发布

站内文章 / 模拟电子
10475 0 1497
    这本来是5.1前写的一个算法，可是一直没写好。因为数论这里有点东西没弄清楚，导致这个小问题搁置了很久（也因为还有其他事情要做，摊子铺的太大了）。最近做事情注意力不够集中，效率比较低，希望通过描述一下此算法，理理思路。
      规范起见，还是先描述一下该问题：求一个数的幂ab mod n （a,b和n是正整数）。描述完毕~
      其实硬算也是可以的，如果怕溢出，可以先求到一定范围，把结果存起来，再接着算...
      我这里还是把“硬算法”的具体方法描述一下吧：假设你的计算机只能取值到M，则当at              ab=at * ab-t ；
             ab mod n=（at * ab-t）mod n;
             由公式：(a * b) mod c=((a mod c)* b) mod c
             得  （at * ab-t）mod n=((at mod n)* ab-t) mod n;
      只要at       好了，这种方法没有人会去用的。

     另外两种比较“理智”的方法（或者说是一种，因为原理都是相同的，只不过形式不一样），首先将 b转化为二进制数：（bk , bk-1, bk-2 ...... b1, b0 ,)             方法1：（我以实例为例，因为说到底还是实例才能说清楚）          a=5;b=22;c=50;(其实a 和 c 取多少都和这里要说的没什么关系，只要看b就可以了) b的二进制表示为10110。         如果从右往左遍历该二进制序列，则第一位是0；若一个数的二进制表示中末尾为0，说明什么？对~~说明该数是能够被2整除的。那么        ab = aA*2  (b=2A)     则ab mod n =( aA * aA ) mod n     根据上面的公式: (a * b) mod c=((a mod c)* b) mod c     得 ( aA * aA ) mod n = ((aA  mod n) * aA) mod n (一步一步写的我好辛苦)
        aA 是啥？对~~ aA 不就是10110 右移一位嘛，就是1011（右移一位等于原数除以2，这个不用我说了吧）。     那么，就是从右往左遍历到第二位了。第二位是1，说明什么？对~~说明这个数不能被2整除…则 aA =aB+1(A=B+1),     即 aA =aB * a     那么，aA  mod n =((aB mod n) * a ) mod n         aB是多少？对~~  其实 B不已经是偶数了嘛。     用之前的方法类推，aB mod n = ((aC  mod n) * aC) mod n （B=2C）     原式 aA  mod n =((aB mod n) * a ) mod n = (((aC  mod n) * aC ) mod n) * a ) mod c （注意区分大小写，A，B，C和原来的a,b,c不是一回事）        aC 又是啥？以此类推。一直将二进制序列右移，反复嵌套，直到最后一位，就OK啦！ 代码如下：         int a,b,c;         输入a,b,c的值         int t=a;
    while (b>0)
    {
        if (b%2==1)
        {
            d=(d*t)%n;
        }
        b=b/2;
        t=(t*t)%n;
    }
              好累，明天再写方法2

热门文章