离散对数算法

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'以模数计算时).