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$?
0
$\begingroup$
$\endgroup$
-
1$\begingroup$ citeseer.ist.psu.edu/viewdoc/… $\endgroup$ – user12859 Feb 27 '17 at 8:26
5
$\begingroup$
$\endgroup$
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$.
-
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$ – Tobias Feb 27 '17 at 9:42
