离散对数算法

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)，那么这个naive 实现的时间复杂度为O(n)，那么这个二分查找的时间复杂度肯定为O(log(n) ^2)。或者我对算法的衡量方式有误解吗？编辑：我通常不写二分查找，所以如果有微不足道的实现错误，请忽略它或进行修复。

- Puppy

---

pow 的复杂度是多少？ - Josh Lee

@JoshLee：幂次对数，至多。 - Puppy

试试这个：http://en.wikipedia.org/wiki/Baby-step_giant-step - kilotaras

Answer 1

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

这对于自然数是正确的，但在有限循环群中不起作用（当'pow'模除一些数字时）。

- Daniel

---

这很清楚地解释了我的直觉和真相之间的差异 - 我没有考虑到这一点。 - Puppy