Why does Miller-Rabin algorithm check for perfect powers?

Question

I was reading the following version of the Miller-Rabin algorithm:

it can also be found on page 6 of the following notes. The first if statement checks wether the input $n$ is a perfect power. i.e. wether $$n = b^a $$ is satisfied. My question is, why is that a special case that is checked at the beginning? If we didn't exclude numbers of that form, would the remaining of the algorithm not work? Why do we check that?

Answer 1

The algorithm cannot become wrong if you omit that check. After all its only outputs are "definitely composite" or "possibly prime" and neither of these outputs is wrong for a (necessarily composite) perfect power. Also, the general credibility of the test is based on the fact that repeated tests with independently random initial values $a$ are performed and one can show that at least $\frac34$ of the candidate $a$ do produce "composite" as output of $n$ is composite - no matter if it is a perfect power or not. In fact, perfect powers have unusually many divisors so are likely to be detected quickly anyway.

It seems that the text you reference adds the test only to simplify the proof that the witness probability is at least $\frac12$: At one point they need two nontrivial coprime factors of $n$ in order to apply the Chinese Remainder Theorem, and even for this it suffices that $n$ is not a perfect power of a prime.

Besides,

• for example Wikipedia describes the test without a perfect-power-check.
• for a "random" large input it is very unlikely that it happens to be a perfect power
• Testing for perfect power is more complicated (and possibly error-prone) than just running an additional Miller-Rabin round; all inputs gain from such an additional round whereas only few 8see previous point) gain from a perfect-power-test

Answer 2

The Miller-Rabin test doesn't need a perfect power test. See Crandall and Pomerance pages 135-136 for example.

On the other hand, tests for the input being a perfect square are not uncommon in some Lucas and Frobenius tests. The former generally when searching for parameters where $(P|n)=-1$ which won't ever happen. But typically the test is put off until we've searched a bit, since it isn't very common. C&P page 151 shows Grantham's QFT theorem, which has "Suppose n is a composite [...] and not a square [...]", which means at some point we'd need a perfect square test to get the required error bound. The EQFT algorithms from Damgard and Frandsen contain tests for perfect square and/or cube in the first step. But keep in mind these aren't Miller-Rabin tests.