Efficiently Certifying Non-Integer Powers
We describe a randomized algorithm that, given an integer a, produces a certificate that the integer is not a pure power of an integer in expected (log a)(1+o(1)) bit operations under the assumption of the Generalized Riemann Hypothesis. The certificate can then be verified in deterministic (log a)(1+o(1)) time. The certificate constitutes for each possible prime exponent p a prime number q(p), such that a mod q(p) is a p(th) non-residue. We use an effective version of the Chebotarev density theorem to estimate the density of such prime numbers q(p).
chebotarev density theorem integer roots integer powers linear-time algorithm bit complexity