NO2贴：请教：如何用C实现大数的大数次幂及求模

sh365

对于表达式（数字均为十进制数）： (319570873830358677766204855298122686115^267883928491927118605551155696238269887)/340282366920938463463374607431751499777 该怎么用C编程解决？有什么思路？（a^b表示a的b次幂）
问题出在大数的大数次幂上，这个怎么求解啊？应该不可能硬计算吧。
求高手指点。
谢谢！

bruceteen

化简，对于
(a^b)%c
如果 a >= c，可以简化为
d = a%c
(d^b)%c
否则可以简化为
( ((a^2)^(b/2))%c   * a ) % c

一直这样化下去，最终为
( x * y ) % c

bruceteen

伪代码，这么做使得代码量变多了，但计算量变少了，即运行时间缩短了

1. 
   
2.         // 公式 ( a^b * w ) % c
   
3.         a = 319570873830358677766204855298122686115
   
4.         b = 340282366920938463463374607431751499777
   
5.         c = 340282366920938463463374607431751499777
   
6.         w = 1
   
7. 
   
8.         if( a >= c )
   
9.                 a %= c;
   
10. 
    
11.         for( ; b>0; )
    
12.         {
    
13.                 w = ( (b%2)*a * w )%c;
    
14.                 a = (a*a)%c;
    
15.                 b = b/2;
    
16.         }
    
17. 
    
18.         return w;
    

复制代码

MMMIX

回复 1# sh365


    你如果只是想计算这个，可以用 GMP，如果是想自己实现，也可以参考它的实现。

http://gmplib.org/

sh365

伪代码，这么做使得代码量变多了，但计算量变少了，即运行时间缩短了
bruceteen 发表于 2011-10-28 13:03

Thanks，很好的思路。

sh365

回复 4# MMMIX
Thanks，我学习一下。

鸡丝拌面

从高位到低看b的二进制，如果零那么d（初值为1）乘法模，一则乘d*a 模c。

yulihua49

对于表达式（数字均为十进制数）： (319570873830358677766204855298122686115^26788392849192711860555115 ...
sh365 发表于 2011-10-28 12:47

    这是很普通的算法啊！在ssl里有。

在密码学用的大数是在有限域，应该是大的正整数。

2楼算法的程序实现：

1. #include <stdio.h>
   
2. #include "bignum.h"
   
3. /* ret = a ** z % n */
   
4. u_int *expmod(int n,u_int *a,u_int *z,u_int *m,u_int *ret)
   
5. {
   
6. u_int a1[MAXNUMBER+1];
   
7. u_int z1[MAXNUMBER+1];
   
8. u_int x[MAXNUMBER+1];
   
9.         numcpy(n,a1,a);
   
10.         numcpy(n,z1,z);
    
11.         n_one(n,x);
    
12.         while(!n_iszero(n,z1)) {
    
13.                 while(!(z1[0]&1)) {
    
14.                         rshift(n,z1,1);
    
15.                         /* a1 = (a1 *a1) % m; */
    
16.                         mulmod(n,a1,a1,m,a1);
    
17.                 }
    
18.                 decm(n,z1);
    
19.                 /* x = (x*a1) % m; */
    
20.                 mulmod(n,x,a1,m,x);
    
21.         }
    
22.         numcpy(n,ret,x);
    
23.         return ret;
    
24. }
    

复制代码

数由uint32_t数组表示，n是数组的大小。

其他任何格式表示的数字可以经过转换进入数组。

sh365

回复 8# yulihua49
Thanks,我来学习一下。

0xC1988

二进制转换为10进制可以以2的权值相加（貌似是这样描述的）。比如13=(1101)2=1*2^3+1*2^2+0*2^1+1*2^0。同样的，当我们计算A*B的时候，也可以将B化成2^n相加的式子。于是，我们可以将a*b mod c转换成[a*(2^b0+2^b1+……2^bn)] mod c=[a*2^b0+a*2^b1+……a*2^bn] mod c。利用公式(a+b)mod c=[(a mod c)+(b mod c)]mod c这个公式进行运算