数学不行，看到一段RSA加密程序，关于快速取模的，特来请教下，看了几个小时，搞不懂
这个是一个RSA加密程序的片段，该RSA加密程序对小于100的数加密结果正确，对大于100的数加密结果有偏差。跟踪了一下，提取了以下片段。是一个快速取模的运算。
返回值是M^e%n,也就是m的e次方，再模n。看起来像是整数运算溢出了。
1920^4519 mod 10403 = 10000，结果有问题，计算器无法计算的，1920是加密得到的，用计算器算过加密过程是对的，问题出在解密过程。
int kuaisuqumo(int m,int e,int n){
int i,j,t=0,c=1,b,len=0;
for(i=0;e!=0;i++){
b=e%2;
e=e/2;
len++;
}
for(j=i-1;j>=0;j--){
t=2*t;
c=(c*c)%n;
if(b==1){
t+=1;
c=(c*m)%n;
}
}
return c;
}
int _tmain(int argc, _TCHAR* argv[]){
printf("%d ",kuaisuqumo(1817,4519,10403));//结果打印了9897，是正确的
printf( "%d",kuaisuqumo(1920,4519,10403) );//结果打印了10000，正确应该是10099
}
http://cache.amobbs.com/bbs_upload782111/files_49/ourdev_704455COYP3G.jpg
(原文件名:2.jpg)
http://cache.amobbs.com/bbs_upload782111/files_49/ourdev_704456K8420L.jpg
(原文件名:3.jpg)
算法原理百度文库有介绍，不过看不太懂。http://wenku.baidu.com/view/cf2d6b651ed9ad51f01df21a.html
付上VC工程，哎，看了几个小时，找不到问题所在
VC工程ourdev_704457UXF0AJ.rar(文件大小:136K) (原文件名:RSA.rar) 回复【楼主位】lihui_mc软硬兼施
-----------------------------------------------------------------------
版面的代码格式都没缩进了，上传个图好看点
http://cache.amobbs.com/bbs_upload782111/files_49/ourdev_704458MNCS7G.jpg
(原文件名:5.jpg) 搞错了，正确结果应该是99100，不过它返回了10000仍然是有问题的 回复【2楼】lihui_mc 软硬兼施
搞错了，正确结果应该是99100，不过它返回了10000仍然是有问题的
-----------------------------------------------------------------------
正确结果应该小于10403,所以99100肯定不正确. 貌似10000是正确的
http://acme.com/software/bigint/bic.cgi?expr=modpow%281920%2C4519%2C10403%29
===========================================================================
bic results
% bic
modpow(1920,4519,10403)
10000
Try another
===========================================================================
http://acme.com/software/bigint/
google "modular exponentiation calculator", 找个计算器先验证下吧~~ 回复【4楼】root菜鸟活化石
-----------------------------------------------------------------------
原来如此，谢谢提醒了，问题找到了呵，出错是出在数据分组，将97和98组合，结果是97*100+98=9798，而将99和100组合，结果是99*100+100=10000，溢出了，作者源程序只能支持两位10进制组合的，因此超过了100就溢出了。 MARK RSA
页:
[1]