7
$\begingroup$

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

$\endgroup$

3 Answers 3

11
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Ha, you type faster! $\endgroup$ Sep 4, 2012 at 8:59
  • $\begingroup$ Perfect! I was hoping the answer was that simple. Thanks! $\endgroup$ Sep 4, 2012 at 9:10
  • 1
    $\begingroup$ 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. $\endgroup$ Sep 4, 2012 at 11:48
  • $\begingroup$ @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?" $\endgroup$
    – Mark Lewko
    Sep 4, 2012 at 18:20
  • 1
    $\begingroup$ Yes, but from the context it is clear that that’s not what Shor actually uses in the paper. $\endgroup$ Sep 5, 2012 at 11:30
12
$\begingroup$

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

$\endgroup$
9
$\begingroup$

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

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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