Integer root extracting

[Paul Zimmermann]

> From: Torbjorn Granlund <tg at gmplib.org>
> Date: Fri, 03 Sep 2010 12:27:30 +0200
> 
> Hans Aberg <haberg-1 at telia.com> writes:
> 
>   GMP has a function mpz_perfect_power_p() that for given integer a
>   tells if a = x^y is solvable in integers x, y with y > 1. But I need
>   to find the largest y for which this is true (and also finding x). One
>   way to do this is to prime factor a and take the gcd of the exponents,
>   but is there a faster method?
>   
> Completely factoring a is of course not always possible.
> 
> A more tractable algorithm is the following:
> 
> for y = floor(log(a)/log(2)) to 2 by -1
>   If a^(1/y) is an integer, return y
> 
> The starting value is the largest power y for which a^(1/y) >= 2.
> 
> Testing if a^(1/y) can be done efficienty by computing mod some small
> numbers; thus most non-solutions can be quickly rejected.
> 
> -- 
> Torbjörn

you can restrict to prime exponent y. See Algorithm IsPower page 29 of [1],
and the comment just below.

Paul Zimmermann

[1] Modern Computer Arithmetic, Richard Brent and Paul Zimmermann,
version 0.5.3, August 2010, http://www.loria.fr/~zimmerma/mca/mca-cup-0.5.3.pdf.