Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
add comment

3 Answers

up vote 4 down vote accepted

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 produces the factorization.

share|improve this answer
    
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
add comment

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

share|improve this answer
add comment

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^n$. This gives a time complexity polynomial in $\log_2 n$, also known as "efficient".

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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