Algoritmo del logaritmo discreto

Question

A menudo he visto que el logaritmo discreto es un problema difícil. Sin embargo, no veo muy bien cómo podría ser esto. Me parece que una búsqueda binaria regular sería suficiente para cumplir este propósito. Por ejemplo,

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

Si la aplicación ingenua de simplemente incrementar p hasta pow(base, p) es O (n), entonces seguramente esta búsqueda binaria es O (log (n)^2).

¿O no entiendo cómo se mide este algoritmo?

Editar: Por lo general, no escribo búsquedas binarias, por lo que si hay algún error de implementación trivial, amablemente solo ignórelo o edítelo en una solución.

Answer 1

Su algoritmo supone que un < b implica pow (base, a) < pow (base, b).

Esto es cierto para números naturales, pero no funcionará en un grupo cíclico finito (cuando 'pow' se calcula modulo algún número).