Integer root extracting

[Hans Aberg]

On 3 Sep 2010, at 12:27, Torbjorn Granlund wrote:

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

I need to extract the root as well, so one can apply mpz_root()  
iteratively for the primes 2, 3, ..., p, as long as p <= log_2 a,  
though its value will only be used if the computation is exact.