# Algorithm for detecting prime powers

While reading Peter Shor's paper Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, I came across the following quote:

"This scheme will thus work as long as $n$ is odd and not a prime power; finding factors of prime powers can be done efficiently with classical methods."

I have two questions:

(1) How does one efficiently determine if a given number $N$ is a prime power, and

(2) How does one efficiently determine the factorization of a prime power?

(Note: I have included these as separate questions since I am aware that many of the standard algorithms for determining a number is composite will not necessarily produce a proper factor.)

If N is a prime power it is of the form $$p^i$$ where $$i \leq \log_2(N)$$. One can thus compute each of the first $$\log_2(N)$$ roots of $$N$$, and test if the resulting number is (first an integer) and then if it is a prime using the AKS algorithm (although perhaps Shor meant to use a randomized test, such as Miller–Rabin, as the paper pre-dates AKS). Obviously if $$N$$ is a prime power this will produce the factorization.

• Ha, you type faster! – Andrej Bauer Sep 4 '12 at 8:59
• Perfect! I was hoping the answer was that simple. Thanks! – Xander Faber Sep 4 '12 at 9:10
• You don’t need AKS or any randomized test. If you want to factor a number (or test it for primality: in fact, the AKS algorithm itself starts by such a check), you can as well check for any perfect powers rather than just prime powers: if you succeed, you get a proper factor of $N$, otherwise you are guaranteed that it is not a prime power. – Emil Jeřábek Sep 4 '12 at 11:48
• @Emil, I agree that one can easily test if a number is a perfect power, however the question was "How does one efficiently determine if a given number is a prime power?" – Mark Lewko Sep 4 '12 at 18:20
• Yes, but from the context it is clear that that’s not what Shor actually uses in the paper. – Emil Jeřábek Sep 5 '12 at 11:30

See Dan Bernstein's paper, Detecting perfect powers in essentially linear time.'' Mathematics of Computation 67 (1998), 1253--1283, available at http://cr.yp.to/papers.html#powers. Here "linear" means "linear in log n".

If $$n = p^k$$ with $$p \geq 2$$ then $$k \leq \log_2 n$$. For each candiate $$k$$, we can compute the integral part of $$m = \lfloor n^{1/k} \rfloor$$ in time polynomial in $$\log_2 n$$, and then test whether the $$n = m^k$$. This gives a time complexity polynomial in $$\log_2 n$$, also known as "efficient".

• Do you not mean $n=m^k$ ? – IntegrateThis May 28 '19 at 5:13
• @IntegrateThis: Yes, thanks, I fixed it. – Andrej Bauer May 28 '19 at 7:54