Suppose that I am given as input the number $p^i$ for some prime $p$ and some positive integer $i$. I wish to find $p$ and $i$.Is there an algorithm to do this that works in time polynomial in the number of digits of $p^i$?
Given a prime power, is it possible to efficiently compute the prime
algorithms;primes
Yes, here is a simple approach (there are likely more efficient ones).Let $n$ be the number given. Observe that $2 \leq p \leq n$ and $1 \leq i \leq \log_2(n)$. For each possible value of $i$ in the range $\{1, \ldots, \log_2(n)\}$, you can do a binary search for a $p$ in the range $\{2, \ldots, n\}$ such that $p^{i} = n$. 