模运算
整数取模实际是基于除法运算的结果,即求余数的过程,把商排除在外后得到的结果。根据已经得到的除法运算结果进行筛选结果即可。
/*
模数运算
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;
}