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$?
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this communitySuppose 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$?
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$.