Summary: 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^{\text{th}}$ non-residue. We use an effective version of the Chebotarev density theorem to estimate the density of such prime numbers $q_{p}$.