2

我尝试计算以下算法的时间复杂度。

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)

4

1 回答 1

2

您的分析可以更详细，并使用更好的数字乘法界限。它应该包含更多关于您从哪里得到所用程序的复杂性的详细说明。

对于大数字相乘，您可以使用Karatsuba 算法或Schönhage–Strassen 算法达到O(n^1.585)或降低（有关详细信息，请参阅链接的维基百科页面）。

构造一个新整数并计算模数N的复杂性不会比线性差。

因此，程序的复杂性encrypt将取决于选择的乘法算法。

程序也是如此decrypt()。我不知道你从哪里得到复杂性modinverse。最多可以计算模乘逆O(n^2)。

维基百科页面中给出的模逆的复杂度为O(log(M)^2)，它使用数字的值表示，为此，我们计算逆。您的分析（通常在处理数论算法时进行）使用数字长度而不是它们的值，这就是复杂性的原因O(N^2)。

于 2013-01-30T23:35:00.137 回答