我试图了解以下算法的时间复杂度 (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 是从哪里来的,二进制数字是什么意思?
最佳答案
运行时间取决于 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。阶数是发生之前的乘法次数。
关于algorithm - 寻找离散对数的时间复杂度(蛮力),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/48232624/