algorithm - 离散对数算法

Question

我经常看到离散对数是一个难题。但是，我不太明白这是怎么回事。在我看来，常规的二进制搜索就可以很好地满足这个目的。例如，

binary_search(base, left, right, target) {
    if (pow(base, left) == target) 
        return left;
    if (pow(base, right) == target)
        return right;
    if (pow(base, (left + right) / 2) < target)
        return binary_search(base, (left + right) / 2, right, target);
    else
        return binary_search(base, left, (left + right) / 2, target);
}   

log(base, number) {
    left = 1;
    right = 2;
    while(pow(base, p) < number) {
        left = right;
        right *= 2;
    }
    return binary_search(base, left, right, number);
}

如果仅递增 p 直到 pow(base, p) 的简单实现是 O(n)，那么这个二分查找肯定是 O(log(n) ^2).

还是我不明白这个算法是怎么衡量的？

编辑:我通常不写二进制搜索，所以如果有一些微不足道的实现错误，请忽略它或编辑修复。

Answer 1

您的算法假定 a < b 意味着 pow(base, a) < pow(base, b)。

这对于自然数是正确的，但它不适用于有限循环群(当“pow”以某个数为模计算时)。