亚洲av成人无遮挡网站在线观看,少妇性bbb搡bbb爽爽爽,亚洲av日韩精品久久久久久,兔费看少妇性l交大片免费,无码少妇一区二区三区

Chinaunix

標(biāo)題: NO2貼：請(qǐng)教：如何用C實(shí)現(xiàn)大數(shù)的大數(shù)次冪及求模 [打印本頁]
作者: sh365    時(shí)間: 2011-10-28 12:47
標(biāo)題: NO2貼：請(qǐng)教：如何用C實(shí)現(xiàn)大數(shù)的大數(shù)次冪及求模
對(duì)于表達(dá)式（數(shù)字均為十進(jìn)制數(shù)）： (319570873830358677766204855298122686115^267883928491927118605551155696238269887)/340282366920938463463374607431751499777 該怎么用C編程解決？有什么思路？（a^b表示a的b次冪）
問題出在大數(shù)的大數(shù)次冪上，這個(gè)怎么求解�。繎�(yīng)該不可能硬計(jì)算吧。
求高手指點(diǎn)。
謝謝！
作者: bruceteen    時(shí)間: 2011-10-28 12:54
化簡(jiǎn)，對(duì)于
(a^b)%c
如果 a >= c，可以簡(jiǎn)化為
d = a%c
(d^b)%c
否則可以簡(jiǎn)化為
( ((a^2)^(b/2))%c   * a ) % c

一直這樣化下去，最終為
( x * y ) % c
作者: bruceteen    時(shí)間: 2011-10-28 13:03
偽代碼，這么做使得代碼量變多了，但計(jì)算量變少了，即運(yùn)行時(shí)間縮短了

  2.         // 公式 ( a^b * w ) % c
  3.         a = 319570873830358677766204855298122686115
  4.         b = 340282366920938463463374607431751499777
  5.         c = 340282366920938463463374607431751499777
  6.         w = 1

  8.         if( a >= c )
  9.                 a %= c;

  11.         for( ; b>0; )
  12.         {
  13.                 w = ( (b%2)*a * w )%c;
  14.                 a = (a*a)%c;
  15.                 b = b/2;
  16.         }

  18.         return w;
復(fù)制代碼
作者: MMMIX    時(shí)間: 2011-10-28 13:15
回復(fù) 1# sh365


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

http://gmplib.org/
作者: sh365    時(shí)間: 2011-10-28 13:43
偽代碼，這么做使得代碼量變多了，但計(jì)算量變少了，即運(yùn)行時(shí)間縮短了
bruceteen 發(fā)表于 2011-10-28 13:03

Thanks，很好的思路。
作者: sh365    時(shí)間: 2011-10-28 13:45
回復(fù) 4# MMMIX
Thanks，我學(xué)習(xí)一下。
作者: 雞絲拌面    時(shí)間: 2011-10-28 15:31
從高位到低看b的二進(jìn)制，如果零那么d（初值為1）乘法模，一則乘d*a 模c。
作者: yulihua49    時(shí)間: 2011-10-28 15:42
本帖最后由 yulihua49 于 2011-10-28 15:53 編輯
對(duì)于表達(dá)式（數(shù)字均為十進(jìn)制數(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)換進(jìn)入數(shù)組。
作者: sh365    時(shí)間: 2011-10-29 16:46
回復(fù) 8# yulihua49
Thanks,我來學(xué)習(xí)一下。
作者: 0xC1988    時(shí)間: 2011-10-29 17:01
二進(jìn)制轉(zhuǎn)換為10進(jìn)制可以以2的權(quán)值相加（貌似是這樣描述的）。比如13=(1101)2=1*2^3+1*2^2+0*2^1+1*2^0。同樣的，當(dāng)我們計(jì)算A*B的時(shí)候，也可以將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這個(gè)公式進(jìn)行運(yùn)算
作者: davelv    時(shí)間: 2011-10-29 17:16
4樓大人說的沒錯(cuò)。gmp里面有封裝好的大整數(shù)，還能直接用RSA加密～



歡迎光臨 Chinaunix (http://www.72891.cn/) Powered by Discuz! X3.2