<p>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$.</p>

<p>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?</p>

<p>[1]: <a href="http://www.ams.org/journals/mcom/2007-76-257/S0025-5718-06-01837-0/" rel="nofollow">Bernstein, Lenstra, and Pila. <em>Detecting Perfect powers by factoring into coprimes</em>, 2006.</a></p>

CC BY-SA 3.0
2012-11-07T11:20:56.720Z
Is “some number p” a typo for “some prime p”?
Tsuyoshi Ito
CC BY-SA 3.0
2012-11-07T13:50:52.463Z
The title is misleading. Discrete log refers to modular arithmetic.
Emil Jeřábek
CC BY-SA 3.0
2012-11-07T16:35:58.537Z
@TsuyoshiIto Yes, that was a typo, thank you.
argentpepper
CC BY-SA 3.0
2012-11-07T16:37:25.110Z
@EmilJeřábek I will change it.
argentpepper
<cc.complexity-theory><time-complexity><nt.number-theory><primes>
Complexity of computing logarithm of a prime power
argentpepper
# Complexity of computing logarithm of a prime power

(Asked by: username_0 on 2012-11-07)

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.](http://www.ams.org/journals/mcom/2007-76-257/S0025-5718-06-01837-0/)

**Tags:** cc.complexity-theory, time-complexity, nt.number-theory, primes
> **Comments:**
> **username_1**: Is “some number p” a typo for “some prime p”?  
> **username_2**: The title is misleading. Discrete log refers to modular arithmetic.  
> **username_0**: @TsuyoshiIto Yes, that was a typo, thank you.  
> **username_0**: @EmilJeřábek I will change it.  

---

## 0 answers

