mpz_perfect_power_p()

[Paul Leyland]

> Also, given that this function tells us that some candidate is a =
perfect
> power, can we then easily determine the value of that perfect power ? =
I
> guess not .... otherwise the function would surely return that value.

Surely, if you know that N =3D a^x with a not necessarily prime, it's =
then extremely easy to discover a and x with very little code and in a =
very short time.   The obvious approach is to use Newton-Raphson to find =
the x-th root, b say, by successively trying x=3D2, x=3D3, ... x =3D =
floor(log_2(N)) until you find a value for which b^x=3DN.

When you have that you need only to factor b, if it's not prime.  Unless =
N is excessively large, this ought to be straightforward.

Yes, I know that the search outlined above can be short-circuited.   My =
point is that it's almost always very easy to factor N given that it's a =
perfect power.


Paul