我想知道RSA算法如何处理这么大的数字和
tried one example in WolframAlpha.他们如何处理这样的疯狂数字？
编辑：只是为了使它更奇怪,one more example
解决方法
有一个简单的算法叫做
exponentiation by squaring,可以非常有效的计算ab modc.这是基于这样的观察
a2k mod c = (ak)2 mod c
a2k + 1 mod c = a · (ak)2 mod c
鉴于此,您可以使用递归方法计算ab modc：
function raiseModPower(a,b,c):
if b == 0 return 1
let d = raiseModPower(a,floor(b/2),c)
if b mod 2 = 1:
return d * d * a mod c
else
return d * d mod c
这只有O(log b)乘法,其中每个都不能有比O(log c)更多的数字,所以它真的很快.这就是RSA实现如何将事情提升到权力.如果您愿意,可以将其重写为迭代,尽管我认为递归演示文稿真的很干净.
一旦有了这个算法,就可以使用标准技术来乘以任意精度数来进行计算.由于只需要O(log b)的乘法迭代(与b迭代相反),所以这是快速的.你从来没有真正结束计算ab,然后用c修改它,这也保持数字的数字低,并使其更快.
希望这可以帮助！
