C++ 怎么计算会溢出的大数乘方

答案:3 悬赏:30 手机版

解决时间 2021-04-08 23:24

提问者网友：鐵馬踏冰河
2021-04-08 04:15

加密算法中需要计算两个数的乘方，两个数会很大，肯定溢出（例如3的93次方）。请问怎么处理这样的数据？不是RSA里的乘方再模除，不模除，需要乘方结果参与后面的运算
就这么多分了，求大神指点。

最佳答案

五星知识达人网友：woshuo
2021-04-08 05:49

如果你坚持要算这么大的数，那就先分配足够的空间，比如说3^93，就至少要17字节的内存，分段相乘，每次加上进位项，你可以参考以前4字节整形数据乘法的实现方式（以前是16位的寄存器，一次只能处理16位的数据，所以要分段处理）。不过还是建议你优化算法，尽量不算这么大的数。

全部回答

1楼网友：梦中风几里
2021-04-08 08:05

可以当作字符串来处理。你可以试着用二分法尝试一下，具体我没做过。先写一个大数乘法函数，输入输出全是字符串。然后，用二分法。比如求50000的开平方，先试5000/2=2500，2500*2500>5000，于是试 2500/2=1250, 1250*1250>5000, 于是试 1250/2=625, …… …… 试 156/2=78, 78*78>5000, 于是试 78/2=39, 39*39<5000, 于是可以定位在39-78之间，试（39+78)/2=57, 57*57<5000, 于是可以定位在57-78之间，试（57+78）/2=67，67*67<5000,于是可以定位在67-78之间，试（67+78）/2=72, 72*72>5000, 于是可以定位在67-72之间 …… 最后定位在70-71之间，至于取哪个，看你怎么选了。这是我写的一个求阶乘的函数，不知道对你有没有帮助。 #include <stdio.h> #include <math.h> #define len 1000 void multi_string(char *data_s1, char *data_s2, char *data_product); void multi_string_single(char *data_s, char ch, char *data_sum); void add_string(char *data_s1, char *data_s2, char *data_sum, int len_sum); int ctoi(char ch); char itoc(int data); void shift_left(char *data, int num); void factorial(int order, char *pro_result); int ctoi(char ch) { switch(ch) { case '0' : return 0; case '1' : return 1; case '2' : return 2; case '3' : return 3; case '4' : return 4; case '5' : return 5; case '6' : return 6; case '7' : return 7; case '8' : return 8; case '9' : return 9; default : return 0; } } char itoc(int data) { switch(data) { case 0 : return '0'; case 1 : return '1'; case 2 : return '2'; case 3 : return '3'; case 4 : return '4'; case 5 : return '5'; case 6 : return '6'; case 7 : return '7'; case 8 : return '8'; case 9 : return '9'; default : return '0'; } } void multi_string_single(char *data_s, char ch, char *data_pro) { int times; int i,j,k; int len, len_0; int len_pro_0; int sum_tmp; int carry; int add_bits; len = 0; len_0 =0; len_pro_0 = 0; times = ctoi(ch); while(data_s[len_0]=='0') { len_0++;} while(data_pro[len_pro_0]=='0') { len_pro_0++;} while(data_s[len]!='\0') { len++; } for(i=0;i<len;i++) { data_pro[i] = '0'; } carry = 0; sum_tmp = 0; add_bits = 0; for(k=0;k<times;k++) { carry = 0; for(i=0;i<len - len_0 + add_bits;i++) { sum_tmp = ctoi(data_pro[len-1-i]) + ctoi(data_s[len-1-i]) + carry; data_pro[len-1-i] = itoc( sum_tmp % 10 ); carry = sum_tmp/10; } if(carry==1) { add_bits++; data_pro[len-1-i] = itoc(carry); } } return; } void add_string(char *data_s1, char *data_s2, char *data_sum, int len_sum) { int i,j,k; int carry; int sum_tmp; int len1,len2; char data_s1_bit; char data_s2_bit; len1=0; len2=0; while(data_s1[len1]!='\0') {len1++;} while(data_s2[len2]!='\0') {len2++;} carry = 0; for(i=0;i<len_sum;i++) { if(i>=len1) { data_s1_bit = '0'; } else { data_s1_bit = data_s1[len1-1-i]; } if(i>=len2) { data_s2_bit = '0'; } else { data_s2_bit = data_s2[len2-1-i]; } sum_tmp = ctoi(data_s1_bit) + ctoi(data_s2_bit) + carry; data_sum[len_sum-1-i] = itoc( sum_tmp % 10 ); carry = sum_tmp/10; } return; } void shift_left(char *data, int num) { int i; int len; len=0; while(data[len]!='\0') {len++;} for(i=0;i<len;i++) { if(i<len-num) { data[i] = data[i+num]; } else { data[i] = '0'; } } return; } void multi_string(char *data_s1, char *data_s2, char *data_product) { char data_pro_tmp[len+1]; char data_pro_single_tmp[len+1]; unsigned int len1_0, len2_0; unsigned int len1, len2; unsigned int len_pro; int i,j,k; len1_0 = 0; len2_0 = 0; len1 = 0; len2 = 0; while(data_s1[len1_0]=='0') { len1_0++; } while(data_s2[len2_0]=='0') { len2_0++; } while(data_s1[len1]!='\0') { len1++; } while(data_s2[len2]!='\0') { len2++; } for(i=0;i<len;i++) { data_pro_tmp[i] = '0'; data_pro_single_tmp[i] = '0'; } data_pro_tmp[i] = '\0'; data_pro_single_tmp[i] = '\0'; for(k=0;k<len2-len2_0;k++) { multi_string_single(data_s1, data_s2[len2-1-k], data_pro_single_tmp); shift_left(data_pro_single_tmp, k); add_string(data_pro_single_tmp, data_pro_tmp, data_pro_tmp, len); } for(i=0;i<len;i++) { data_product[i] = data_pro_tmp[i]; } return; } void factorial(int order, char *pro_result) { int i,j; char added_number[len+1]; pro_result[len] = '\0'; added_number[len] = '\0'; for(i=0;i<len-1;i++) { added_number[i] = '0'; pro_result[i] = '0'; } added_number[len-1] = '1'; pro_result[i] = '1'; for(j=0;j<order;j++) { multi_string(added_number, pro_result, pro_result); add_string(added_number, "1", added_number, len); } return; } main() { char pro_result[len+1]; char added_number[len+1]; int len; int i,j,k; int order; char judge; /* char s1[len+1] = "00000

2楼网友：话散在刀尖上
2021-04-08 06:37

若求(a * b) % c，设 a % c = i, b % c = j，则 a = m * c + i, b = n * c + j (m, n为整数) 推导可知： a * b = (m * c + i) * (n * c + j) = (m*n*c + m*j + n*i) * c + i * j 则 (a * b) % c = (i * j) % c 总结就是： (a*b) % c = ((a%c) * (b%c)) % c 所以，只要把a^b×c^d适当分组，每组乘积分别取模后相乘，然后再取模。结果是一样的，同时避免溢出。

我要举报

如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！

点此我要举报以上问答信息