If the number under test 'n' is small, you can find
the first root, second root,...,k th root of n >0. If
any of them is a whole number, then we have a perfect
power. Though the convential algorithm is polynomial
in time, there appears to be a linear time algorithm
for determining perfect powers. Please try the one
D. Berstein, "Detecting perfect powers in essentially
linear time," Math. Comp., 67:223 (1998) 1253--1283.
--- Elena Erbiceanu <shiana_heavens@...
> I am working on the implementation of the AKS
> primality test for large numbers, using a big-int
> library (MpNT).
> I am not sure yet which approach I should use for
> perfect power testing. Almost everyone seems to
> "conveniently" forget about it when implementing the
> I am inclined to work with the PPT presented by
> J. Bernstein in his papers.
> Still, I may not know everything on the subject, so
> would be very happy to hear any suggestions.
> All the best,
> Elena Erbiceanu
Do You Yahoo!?
Tired of spam? Yahoo! Mail has the best spam protection around