rsa：大整数相乘的问题

folklore

回复 2# keymirage


    我们并不需要 e^x （x=0,1,2,3...n）,只要有e^x mod n就可以了。

action08

听说mit出了高科技，已经被量子计算机轻松破解了

cjaizss

keymirage 发表于 2016-03-06 15:32
楼上，那不是废话吗？我脑袋都想破了，就是要算 c =p^e mod n !!!!
要真懂的话，给点提示吧

n这个数如果是X位可以存储
那么 a^b mod n 不是也可以用n位存储吗?

cjaizss

keymirage 发表于 2016-03-07 13:10
楼上，不太明白你的意思。因为c=p^e % n 这个式子里，c,p,e,n这4个数都是1024位的（也就是c跟n是位数相同的 ...

意思是,你不需要存p^e
这个根本不用计算.
令
k=p%n
则
伪码大致
c=1;
for n=0:1023
if(e & (1<<n))
    c = (c*k)%n
end
k=k*k%n;
end
最后c就是p^e%n

cjaizss

keymirage 发表于 2016-03-07 13:10
楼上，不太明白你的意思。因为c=p^e % n 这个式子里，c,p,e,n这4个数都是1024位的（也就是c跟n是位数相同的 ...

意思是,你不需要存p^e
这个根本不用计算.
令
k=p%n
则
伪码大致
c=1;
for n=0:1023
if(e & (1<<n))
    c = (c*k)%n
end
k=k*k%n;
end
最后c就是p^e%n