算法的时间复杂度如何计算、加密和解密？
算法的时间复杂度如何计算、加密和解密？
提问于 2013-01-30 22:56:09
我尝试为下面的算法计算时间复杂度。
private void encrypt()
{
M = new BigInteger(64,random);
C = M.multiply(k).mod(N); // O(n^2)
}
private void decrypt()
{
kk= k.modinverse(N); // O(n^3)
Mp = kk.multiply(c).mod(N); //O(n^2)
}我算过时间复杂度了吗？
其中加密的时间复杂度为O(n^2)，解密的时间复杂度为O(n^3) + O(n^2) = O(n^3)
回答 1
Stack Overflow用户
发布于 2013-01-30 23:35:00
您的分析可以是、更详细的和，使用更好的界进行数字乘法。它应该包含更多关于使用过程的复杂性是从哪里得到的详细说明。
要使大数字成倍增长，您可以使用Karatsuba算法或Sch nhage-Strassen算法获取O(n^1.585)或更低的数据(有关详细信息，请参阅链接的维基百科页面)。
构造一个新的整数并计算结果模N的复杂度不会比线性差。
因此，encrypt过程的复杂性将取决于选择的乘法算法。
decrypt()过程也是如此。我不知道modinverse的复杂性是从哪里来的。模乘逆最多只能在O(n^2)中计算。
给出了维基百科页面中模逆的复杂度，给出了O(log(M)^2)，它用数的值来表示，并对其求逆。您的分析(通常是在处理数论算法时完成的)使用数字长度而不是它们的值，这使得复杂性O(N^2)。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/14615444
复制相关文章
相似问题
腾讯云开发者
