Algorytm logarytmiczny dyskretny

Question

Często widziałem, że dyskretny logarytm jest trudnym problemem. Jednak nie bardzo rozumiem, jak to możliwe. Wydaje mi się, że zwykłe wyszukiwanie binarne dobrze sobie poradziłoby w tym celu. Na przykład,

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); 
} 

Jeśli naiwny realizacja tylko zwiększając p aż pow(base, p) wynosi O (n), to z pewnością tego wyszukiwania binarnego wynosi O (log (n)^2).

Czy nie rozumiem, w jaki sposób jest mierzony ten algorytm?

Edytuj: Zazwyczaj nie piszę wyszukiwań binarnych, więc jeśli wystąpił jakiś drobny błąd w implementacji, po prostu zignoruj ​​go lub edytuj w poprawce.

Answer 1

Twój algorytm zakłada, że ​​< b oznacza pow (podstawa, a) < pow (podstawa, b).

Dotyczy to liczb naturalnych, ale nie będzie działać w skończonej grupie cyklicznej (gdy "pow" jest obliczane modulo pewna liczba).