Chinaunix

标题: NO2贴：请教：如何用C实现大数的大数次幂及求模 [打印本页]
作者: sh365    时间: 2011-10-28 12:47
标题: NO2贴：请教：如何用C实现大数的大数次幂及求模
对于表达式（数字均为十进制数）： (319570873830358677766204855298122686115^267883928491927118605551155696238269887)/340282366920938463463374607431751499777 该怎么用C编程解决？有什么思路？（a^b表示a的b次幂）
问题出在大数的大数次幂上，这个怎么求解啊？应该不可能硬计算吧。
求高手指点。
谢谢！
作者: bruceteen    时间: 2011-10-28 12:54
化简，对于
(a^b)%c
如果 a >= c，可以简化为
d = a%c
(d^b)%c
否则可以简化为
( ((a^2)^(b/2))%c   * a ) % c

一直这样化下去，最终为
( x * y ) % c
作者: bruceteen    时间: 2011-10-28 13:03
伪代码，这么做使得代码量变多了，但计算量变少了，即运行时间缩短了

  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;
复制代码
作者: MMMIX    时间: 2011-10-28 13:15
回复 1# sh365


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

http://gmplib.org/
作者: sh365    时间: 2011-10-28 13:43
伪代码，这么做使得代码量变多了，但计算量变少了，即运行时间缩短了
bruceteen 发表于 2011-10-28 13:03

Thanks，很好的思路。
作者: sh365    时间: 2011-10-28 13:45
回复 4# MMMIX
Thanks，我学习一下。
作者: 鸡丝拌面    时间: 2011-10-28 15:31
从高位到低看b的二进制，如果零那么d（初值为1）乘法模，一则乘d*a 模c。
作者: yulihua49    时间: 2011-10-28 15:42
本帖最后由 yulihua49 于 2011-10-28 15:53 编辑
对于表达式（数字均为十进制数）： (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    时间: 2011-10-29 16:46
回复 8# yulihua49
Thanks,我来学习一下。
作者: 0xC1988    时间: 2011-10-29 17:01
二进制转换为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这个公式进行运算
作者: davelv    时间: 2011-10-29 17:16
4楼大人说的没错。gmp里面有封装好的大整数，还能直接用RSA加密～



欢迎光临 Chinaunix (http://bbs.chinaunix.net/) Powered by Discuz! X3.2