SIEVE ALGORITHMS FOR PERFECT POWER TESTING

A positive integer n is a perfect power if there exist integers x and k, both at least 2, such that n = x(k). The usual algorithm to recognize perfect powers computes approximate kth roots for k less-than-or-equal-to log2 n, and runs in time O(log3 n log log log n). First we improve this worst-case running time to O(log3 n) by using a modified Newton's method to compute approximate kth roots. Parallelizing this gives an NC2 algorithm. Second, we present a sieve algorithm that avoids kth-root computations by seeing if the input n is a perfect kth power modulo small primes. If n is chosen uniformly from a large enough interval, the average running time is O(log2 n). Third, we incorporate trial division to give a sieve algorithm with an average running time of O(log2 n/log2 log n) and a median running time of O(log n). The two sieve algorithms use a precomputed table of small primes. We give a heuristic argument and computational evidence that the largest prime needed in this table is (logn)1+o(1); assuming the Extended Riemann Hypothesis, primes up to (log n)2+o(1) suffice. The table can be computed in time roughly proportional to the largest prime it contains. We also present computational results indicating that our sieve algorithms perform extremely well in practice.