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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|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.