0
$\begingroup$

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$?

|cite|improve this question
$\endgroup$
5
$\begingroup$

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

|cite|improve this answer
$\endgroup$
  • 3
    $\begingroup$ Note that you might want to iterate over $i$ beginning with $log_2(n)$ instead of $1$. Otherwise, you might find non-primes for $p$ (e.g. $2^{12} = 8^4$). If you start at $log_2(n)$, the first $p$ you find will always be prime. $\endgroup$ – still_learning Feb 27 '17 at 9:42

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.