Complexity of computing logarithm of a prime power

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?

-
Is “some number p” a typo for “some prime p”? –  Tsuyoshi Ito Nov 7 '12 at 11:20
The title is misleading. Discrete log refers to modular arithmetic. –  Emil Jeřábek Nov 7 '12 at 13:50
@TsuyoshiIto Yes, that was a typo, thank you. –  argentpepper Nov 7 '12 at 16:35
@EmilJeřábek I will change it. –  argentpepper Nov 7 '12 at 16:37