超长整数的基础运算 算法实现之模、模幂篇

2019-04-13 16:05发布

模运算 整数取模实际是基于除法运算的结果,即求余数的过程,把商排除在外后得到的结果。根据已经得到的除法运算结果进行筛选结果即可。 /* 模数运算 a 被模数 b 模数 c 模值 */ int modHBInt(HBigInt *a, HBigInt *b, HBigInt *c){ HBigInt tc; //模数不能为0 if(0 == b->length || (1 == b->length && 0 == b->pBigInt[0])) return -1; //模数为1,则模值等于被模数 if(1 == b->length && 1 == b->pBigInt[0]) { setZeroHBInt(c); hbi_add_int(c,0); return RETURN_OK_BINT; } if(-1 == compareHBInt(a,b)) { //模数大于被模数,模值为被模数 assignHBInt(c,a); return RETURN_OK_BINT; } //初始化临时变量 initHBInt(&tc,INITIAL_BINT); divHBInt(a, b, &tc, c); // 回收临时变量空间 deleteHBInt(&tc); return RETURN_OK_BINT; }
模幂运算 由于底数和指数都是大整数,所以采用一般的计算方式(计算幂值后利用除法进行取模)存在严重的效率地下问题,因此在选择算法时必须考虑快速和已处理两部分的因素。在处理该算法时,最核心的部分是降幂运算,所以采用了平方乘取模的原理。
算法流程如下: 输入:3个B进制(位数n、t、p)的大整数x(底数)、y(幂数)、z(模数) 输出:B进制的模值r(初始化r=1) 1.      判断非一般情况下模幂结果: 1.1  z == 0,则返回错误码 RETURN_FAILE_BINT 1.2  z == 1,则r = 0,实际上r = xy ,因为这样的计算失去取模的意义 1.3  y == 1,则r = x % z,即普通的取模运算 1.4  y == 0,则r=1 2.      i从t到0 2.1  y是奇数,则r = r * x % z 2.2  x = x2 % z 2.3  y = y / 2 2.4  根据当前y的长度(位数)来递减i的值 3. 返回r /* 模数运算 a 被模数 p 指数 b 模数 c 模值 */ int modPowerHBInt(HBigInt *a, HBigInt *p, HBigInt *b, HBigInt *c){ HBigInt ta,ta_1,tp,tc,tc_1,demo_one; // 模数为0 if(0 == b->length || (1 == b->length && 0 == b->pBigInt[0])) return -1; // 模数为1,则模值等于被模数,因为没有计算的意义,所以自定义为0 if(1 == b->length && 1 == b->pBigInt[0]) { setZeroHBInt(c); hbi_add_int(c,0); return RETURN_OK_BINT; } if( 1 == p->length && 1 == p->pBigInt[0] ) return modHBInt(a,b,c); else if ( (1 == p->length && 0 == p->pBigInt[0]) || 0 == p->length) { // 指数为0 setZeroHBInt(c); hbi_add_int(c,1); return RETURN_OK_BINT; } else { setZeroHBInt(c); hbi_add_int(c,1); initHBInt(&ta,INITIAL_BINT); initHBInt(&ta_1,INITIAL_BINT); initHBInt(&tp,INITIAL_BINT); initHBInt(&tc,INITIAL_BINT); initHBInt(&tc_1,INITIAL_BINT); initHBInt(&demo_one,INITIAL_BINT); initHBInt(&tp,INITIAL_BINT); extendHBInt(&tc,c->length); extendHBInt(&ta_1,c->length); // 初始化单位1 setZeroHBInt(&demo_one); hbi_add_int(&demo_one,1); // 赋值临时变量 assignHBInt(&tp,p); assignHBInt(&ta,a); extendHBInt(&tc,c->length); extendHBInt(&ta_1,ta.length + ta.length); // 平方乘取摸 while(tp.length){ if (tp.pBigInt[0] & 0x1){ mulHBInt(c,c,&ta); assignHBInt(&tc,c); modHBInt(&tc,b,c); } mulHBInt(&ta_1,&ta,&ta); modHBInt(&ta_1,b,&ta); // 降幂 Right_shift_bit(&tc_1, &tp); assignHBInt(&tp,&tc_1); trimHBInt(&tp); //去除高位无效的0 } } // 回收临时变量空间 deleteHBInt(&ta); deleteHBInt(&ta_1); deleteHBInt(&tp); deleteHBInt(&tc); deleteHBInt(&tc_1); deleteHBInt(&demo_one); return RETURN_OK_BINT; }