以m比特为密钥的RSA加密和解密n比特长的数据的时间复杂度分别为多少？

Sat Sep 30 2023 · json · rss

Subscribe:

RSS

JSON

About

期望时间复杂度计算为：

$f(n,m)=[n/m]*(\frac{m}{2}*f(m,*)+m*f(m,*))$

其中 $f(m,*)$ 指对m比特的进行相乘的复杂度。

在计算机进行乘法计算的时候，传统的计算方法采用了类似竖式计算的方法——正如我们在小学课堂里面所学到的那样，因此时间复杂度是O(n ^ 2)。在进行大数（比如说数字位数超过2048）乘法计算的时候，目前的做法是Schönhage–Strassen算法，该算法利用快速傅里叶变换，将算法的复杂度降到O(n log n log log n)。

最近，Harvey 和Van Der Hoeven 在HAL贴出了两人合著的新论文“Integermultiplication in timeO(n log n)”，宣称已经发现时间复杂度为O(n log n)的整数乘法算法。
作者：留德华叫兽
链接：https://zhuanlan.zhihu.com/p/62143130
来源：知乎
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

在通常意义下，为 $f(n,m)=[n/m]*(1.5*m^3)=O(m^2)$

在极限下，为 $f(n,m)=[n/m]*(1.5*m^2 \log m)=O(n*m\log m)$

空间复杂度包含：

$f(n,m)=n+k*m=O(m+n)$

其中k是常数项，具体取决于算法。