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.

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

0

Reset to default

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.