Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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.

share|improve this question
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.