History

Please fill in your query. A complete syntax description you will find on the General Help page.
Efficiently certifying non-integer powers. (English)
Comput. Complexity 19, No. 3, 355-366 (2010).
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}$.