performance - 如何计算算法的加密和解密时间复杂度？

Question

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

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)

Answer 1

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

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

构造一个新整数并计算对 N 取模的结果，其复杂性不会比线性差。

因此，加密过程的复杂性将取决于所选的乘法算法。

decrypt() 过程也是如此。我不知道你从哪里得到modinverse的复杂性。 Modular multiplicative inverse最多可以计算O(n^2)。

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