我正在学习RSA算法。我在非常小的素数上执行算法，并使用在线大整数计算器执行加密和解密，一切正常。
我的问题是关于我们创建的指数的大小，当涉及到更大的数字时，计算似乎不可行。
例如，该算法从选择两个素数 p 和 q 开始。你计算 n=pxq，然后计算 n 的全能。接下来，您选择一个数字"e"，使得 1
然后要执行加密，您需要像 ASCII 字符"A"(65(一样将其提升到 e 的幂。 (65^e(
当e大于约100,000(6位数字(时，在线大整数计算器开始变得非常缓慢和缓慢(超过一分钟计算(
那么我的问题是，对于有效的RSA算法，该算法选择什么大小(位数(的数字？
我的一个想法是，我使用的在线计算器可能没有使用指数的最佳方法？这是我正在使用的计算器：http://www.javascripter.net/math/calculators/100digitbigintcalculator.htm
假设M是模数。所以是的，你可以先执行intermediate = 65^e，最后计算intermediate mod M。当然，intermediate将是一个非常非常非常大的整数(如果e等于 65537，则intermediate的十进制表示包含 118813 位数字！
但是，由于一个非常基本的模算术定理，
(65^e) mod M = ((((65 mod M) * 65) mod M) * 65) mod M [...] (e times)
(该定理指出，在商环中，元素类的第n次方是元素的n次幂的类(
如您所见，这不需要任何非常大的整数库，因为在每个算术乘积之后，您使用返回0和M-1之间的整数的mod M。因此，您只需计算小于 M 的整数的算术乘积。
例如，下面是一个简单的 shell 脚本 (bash(，它计算 65^65537 mod 991*997。如您所见，无需获取大数字库：
#!/bin/bash
# set RSA parameters
m=65 # message to encode
M=$((991*997)) # modulus (both 991 and 997 are prime numbers)
e=65537 # public exponent (coprime with 990*996, thus compliant with RSA algorithm)
# compute (m^e) mod M
ret=1
for i in {1..$e}
do
ret=$(((ret*m)%M))
done
# display the result
echo $ret
它立即返回784933，因此65^65537 mod 991*997 = 784933
使用您的微积分方法计算的最大整数有 118813 位，但使用此 shell 脚本处理的最大整数只有 12 位或更少的数字((M-1)^2由 12 位数字组成(。
根据这些解释，我们现在可以回答您的问题：
那么我的问题是，对于有效的RSA算法，该算法选择什么大小(位数(的数字？
通过上面的解释，您可以看到您必须操作的整数的十进制表示中的最大位数是1+log10((M-1)^2)，因为您最多将计算0和M-1之间两个整数的乘积。
请注意，1+log10((M-1)^2) = 1+2.log10(M-1) < 2+2.log10(M) = 2.(1+log10(M)).另请注意，1+log10(M)是 M 的位数。
因此，作为结论，这证明了您的函数库必须正确处理的位数是模数的两倍(如果您使用整数乘法计算幂，则按照此处解释的方式(。