A perfect power, and then?

Torbjorn Granlund tg at gmplib.org
Mon Oct 22 22:30:12 CEST 2012


I recently played with the Quadratic Sieve (together with Niels) making
some use of GMP, but of course the bulk of the work in QS is done
sieving using 8-bit numbers.

QS doesn't factor perfect powers, t = a^p.  We can detect such numbers
quickly using mpz_perfect_power_p.  But we cannot get any p satisfying
the equation, except from a loop around mpz_rootrem.  Such a loop is
really slow.

How should we solve this?  It is tempting to let mpz_perfect_power_p
return p, but unfortunately it has type 'int' which might be too small.

Any suggestions for a new function interface?

-- 
Torbjörn


More information about the gmp-devel mailing list