algorithm - 寻找离散对数的时间复杂度(蛮力)

Question

我试图了解以下算法的时间复杂度 (Big-O)，该算法找到 x 使得 g^x = y (mod p) (即找到以 g 为底数 p 的 y 的离散对数)。

这是伪代码:

discreteLogarithm(y, g, p)
    y := y mod p
    a := g
    x := 1

    until a = y
        a := (a * g) mod p
        x++

    return x
end

我知道这种方法的时间复杂度是 p 中二进制数字的指数 - 但这是什么意思，为什么它取决于 p？

我知道复杂度是由循环次数决定的(until a = y)，但是 p 是从哪里来的，二进制数字是什么意思？

Answer 1

运行时间取决于 order g mod p。最坏的情况是阶数(p-1)/2，也就是O(p)。因此，运行时间是 O(p) 模乘。这里的关键是 p 有 log p 位，我在这里使用“log”来表示以 2 为底的对数。由于 p = 2^( log p )——数学恒等式——我们看到运行时间是 p 的位数的指数。为了更清楚，让我们使用 b=log p 来表示位数。最坏情况下的运行时间是 O(2^b) 模乘。模乘需要 O(b^2) 时间，所以完整的运行时间是 O(2^b * b^2) 时间。 2^b 是主导项。

根据您的特定 p 和 g，阶数可能比 p 小得多。然而，分析数论中的一些启发式表明，平均而言，它是 p 阶。

编辑:如果您不熟悉群论中“顺序”的概念，这里有一个简短的解释。如果你一直将 g 乘以自身 mod p，它最终会变成 1。阶数是发生之前的乘法次数。