A perfect power, and then?

[Niels Möller]

Torbjorn Granlund <tg at gmplib.org> writes:

> I just got a crazy idea.  Compute the logarithm of the number (to a few
> bits of precision, perhaps using table lookup).  Multiply this logarithm
> by k.  Exponentiate using the logbase (again using a small table).
> Conservatively compare to number being investigated.

And if desired, one could of course also do that the opposite way: Take
the logarithm of the input number, divide by k, exponentiate, to get a
small range for the highest bits of the kth root. Not sure which variant
would give the best precision (i.e., lowest probability for false
positives).

Ah, and if we're brain storming, yet another variant would be to compute
an extra limb (or maybe only half a limb) of precision when we compute
the 2-adic k'th root. If the extra limb is non-zero, then the input can't
be a k'th power. That's going to asymptotically a bit slower than the
O(1) logarithm trick, but it can have a much smaller false positive
rate.

Regards,
/Niels


-- 
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.