4
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.