Suppose $n = p^k$ for some prime number $p$ and some non-negative integer $k$. What is (the best-known upper bound on) the complexity of computing $k$ on input $n$ (given in binary)? It is important to note that the prime is unknown. The input is just a number $n$.It seems that there exists [1] an algorithm for computing $k$ when $n$ is a power of an arbitrary integer (not necessarily a prime) that runs in $O(\log n \log^c \log n)$ time for some $c$. Is there a better algorithm for prime powers?[1]: Bernstein, Lenstra, and Pila. Detecting Perfect powers by factoring into coprimes, 2006.
Complexity of computing logarithm of a prime power
cc.complexity theory;time complexity;nt.number theory;primes