NO2貼：請教：如何用C實現(xiàn)大數(shù)的大數(shù)次冪及求模

sh365

對于表達式（數(shù)字均為十進制數(shù)）： (319570873830358677766204855298122686115^267883928491927118605551155696238269887)/340282366920938463463374607431751499777 該怎么用C編程解決？有什么思路？（a^b表示a的b次冪）
問題出在大數(shù)的大數(shù)次冪上，這個怎么求解�。繎�(yīng)該不可能硬計算吧。
求高手指點。
謝謝！

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;
    

復(fù)制代碼

MMMIX

回復(fù) 1# sh365


    你如果只是想計算這個，可以用 GMP，如果是想自己實現(xiàn)，也可以參考它的實現(xiàn)。

http://gmplib.org/

sh365

偽代碼，這么做使得代碼量變多了，但計算量變少了，即運行時間縮短了
bruceteen 發(fā)表于 2011-10-28 13:03

Thanks，很好的思路。

sh365

回復(fù) 4# MMMIX
Thanks，我學(xué)習(xí)一下。

雞絲拌面

從高位到低看b的二進制，如果零那么d（初值為1）乘法模，一則乘d*a 模c。

yulihua49

對于表達式（數(shù)字均為十進制數(shù)）： (319570873830358677766204855298122686115^26788392849192711860555115 ...
sh365 發(fā)表于 2011-10-28 12:47

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

在密碼學(xué)用的大數(shù)是在有限域，應(yīng)該是大的正整數(shù)。

2樓算法的程序?qū)崿F(xiàn)：

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. }
    

復(fù)制代碼

數(shù)由uint32_t數(shù)組表示，n是數(shù)組的大小。

其他任何格式表示的數(shù)字可以經(jīng)過轉(zhuǎn)換進入數(shù)組。

sh365

回復(fù) 8# yulihua49
Thanks,我來學(xué)習(xí)一下。

0xC1988

二進制轉(zhuǎn)換為10進制可以以2的權(quán)值相加（貌似是這樣描述的）。比如13=(1101)2=1*2^3+1*2^2+0*2^1+1*2^0。同樣的，當(dāng)我們計算A*B的時候，也可以將B化成2^n相加的式子。于是，我們可以將a*b mod c轉(zhuǎn)換成[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這個公式進行運算