DETECTING PERFECT POWERS BY FACTORING INTO COPRIMES

DANIEL J. BERNSTEIN, HENDRIK W. LENSTRA, JR., AND JONATHAN PILA

Abstract. This paper presents an algorithm that, given an integer n > 1, finds the largest integer k such that n is a kth power. A previous algorithm by the first author took time b^{1+o(1)} where b = lg n; more precisely, time b exp(O(\sqrt{lg b lg lg b})); conjecturally, time b(lg b)^{O(1)}. The new algorithm takes time b(lg b)^{O(1)}. It relies on relatively complicated subroutines—specifically, on the first author’s fast algorithm to factor integers into coprimes—but it allows a proof of the b(lg b)^{O(1)} bound without much background; the previous proof of b^{1+o(1)} relied on transcendental number theory.

Here is an algorithm that, given an integer n > 1, finds the largest integer k such that n is a kth power:

1. For each prime power q such that 2^{q} ≤ n, write down a positive integer r_{q} such that if n is a qth power then n = r_{q}^{q}.

2. Find a finite coprime set P of integers larger than 1 such that each of n, r_{2}, r_{3}, r_{4}, r_{5}, r_{7}, … is a product of powers of elements of P. (In this paper, “coprime” means “pairwise coprime.”)

3. Factor n as ∏_{p∈P} p^{n_{p}}, and compute k = gcd{n_{p} : p ∈ P }. It is easy to see that the algorithm is correct. Say n is an ℓth power. Take any prime power q dividing ℓ. Then n is a qth power, so n = r_{q}^{q}; but r_{q} is a product ∏_{p∈P} p^{a_{p}} for some exponents a_{p}, so n is a product ∏_{p∈P} p^{qa_{p}}. Factorizations over P are unique, so n_{p} = qa_{p} for each p. Thus q divides gcd{n_{p} : p ∈ P } = k. This is true for all q, so ℓ divides k. Conversely, n is certainly a kth power.

Take, for example, n = 49787136 < 2^{26}. Compute approximations

r_{2} = 7056 ≈ n^{1/2}  r_{8} = 9 ≈ n^{1/8}  r_{17} = 3 ≈ n^{1/17}
r_{3} = 368 ≈ n^{1/3}  r_{9} = 7 ≈ n^{1/9}  r_{19} = 3 ≈ n^{1/19}
r_{4} = 84 ≈ n^{1/4}  r_{11} = 5 ≈ n^{1/11}  r_{23} = 2 ≈ n^{1/23}
r_{5} = 35 ≈ n^{1/5}  r_{13} = 4 ≈ n^{1/13}  r_{25} = 2 ≈ n^{1/25}
r_{7} = 13 ≈ n^{1/7}  r_{16} = 3 ≈ n^{1/16}

where ≈ means “within 0.6.” Factor {49787136, 7056, 368, 84, 35, 13, 9, 7, 5, 4, 3, 2} into coprimes: each of these numbers is a product of powers of elements of P = {2, 3, 5, 7, 13, 23}. In particular, n = 2^{8}3^{4}5^{0}7^{4}13^{0}23^{0}, so k = gcd{8, 4, 0, 4, 0, 0} = 4. In other words, n is a 4th power, and is not an ℓth power for ℓ > 4.

Date: 2004.06.30. Permanent ID of this document: bbd41ce71e527d3c06295aadccf60979.

2000 Mathematics Subject Classification. Primary 11Y16.

Initial work: Lenstra was supported by the National Science Foundation under grant DMS– 9224205. Subsequent work: Bernstein was supported by the National Science Foundation under grant DMS–0140542. The authors thank the University of California at Berkeley and the Fields Institute for Research in Mathematical Sciences.

As discussed below, the literature already shows how to perform each step of this algorithm in time b(lg b)^{O(1)}, where b = lg n. Computing n^{1/k}, which is used by some applications, also takes time b(lg b)^{O(1)}.

Details of Step 1. Given n and q, one can use binary search and Newton’s method to compute a floating-point number guaranteed to be within (e.g.) 2^{−32} of n^{1/q}, as explained in [4, Sections 8 and 10]. The algorithms of [4] rely on FFT-based integer multiplication; see [6, Sections 2–4].

Define r_{q} as an integer within 2^{−32} of this floating-point number. If no such integer exists, define r_{q} = 1.

Each r_{q} has O(b/q) bits. Together the r_{q}’s have ∑_{q≤lg n} O(b/q) = O(b lg lg b) bits by Mertens’s theorem. The algorithms of [4] take time (lg b)^{O(1)} per bit.

An alternative approach to Step 1 is to define r_{q} as an integer 2-adically close to n^{1/q}, as explained in [4, Section 21].

Details of Step 2. Given a finite set of positive integers, the algorithm of [5, Section 18] computes the “natural coprime base” for that set. The algorithm takes time s(lg s)^{O(1)} where s is the number of input bits. The algorithm relies on FFTbased multiplication, division, and gcd; see [6, Sections 17 and 22].

Use this algorithm to compute the “natural coprime base” P for {n, r_{2}, … }. Together n, r_{2}, … have O(b lg lg b) bits, so this takes time b(lg b)^{O(1)}.

Details of Step 3. Given a finite coprime set P of integers larger than 1, and given a positive integer that has a factorization over P, the algorithm of [5, Section 20] finds that factorization. The algorithm takes time s(lg s)^{O(1)} where s is the number of input bits. The algorithm relies on FFT-based arithmetic.

Use this algorithm to factor n over P. Together n and P have O(b lg lg b) bits, so this takes time b(lg b)^{O(1)}.

Competition. Previous work by the first author in [4] had already shown that k could be computed in time b^{1+o(1)}. The algorithm of [4] computes r_{q} for prime numbers q, and then computes several increasingly precise approximations to r_{q}^{q}, stopping when an approximation demonstrates that r_{q}^{q} ≠ n.

The run-time bound for the algorithm in this paper has two advantages over the run-time bound for the algorithm in [4]:

• The new bound is smaller. The old bound was b exp(O(\sqrt{lg b lg lg b})); the new bound is b(lg b)^{O(1)}.

• The new proof requires considerably less background. The new proof relies on the first author’s results in [5] on factoring into coprimes, but the old proof relied on deep results in transcendental number theory.

The old algorithm is conjectured to take time b(lg b)^{O(1)}, as discussed in [4, Section 15], but this conjecture seems very difficult to prove.

For typical n’s, both algorithms see from the initial approximation to n^{1/q} that n is not a qth power; the bottleneck is the computation of that approximation. The algorithms behave differently only in the atypical case that n is very close to a power. Optimization of the worst case in more detail than b(lg b)^{O(1)} is beyond the scope of this paper.

History. Bach, Driscoll, and Shallit in [2] introduced a quadratic-time algorithm to factor integers into coprimes. The obvious algorithm takes cubic time.

Bach and Sorenson in [3] published various algorithms to detect perfect powers, i.e., to check whether k > 1. One algorithm takes time O(b^{3}). Another algorithm is conjectured to take time O(b^{2}/(lg b)^{2}) for most, but not all, n’s.

The second and third authors of this paper observed in early 1994 that they could compute k in time O(b^{2}(lg lg b)^{2}) by factoring n, r_{2}, … into coprimes with the Bach-Driscoll-Shallit algorithm; recall that n, r_{2}, … together have O(b lg lg b) bits. This line of work was abandoned several months later when the first author announced that k could be computed in time b^{1+o(1)} by the increasingly-precise-approximations-to-r_{q}^{q} method.

The first author later pointed out that this line of work deserved to be revived, since he had found an essentially-linear-time algorithm—see [5]—to factor integers into coprimes.

References

[1] Eric Bach, James Driscoll, Jeffrey Shallit, Factor refinement, in [7] (1990), 201–211; see also

newer version [2]. URL: http://cr.yp.to/bib/entries.html#1990/bach-cba.

[2] Eric Bach, James Driscoll, Jeffrey Shallit, Factor refinement, Journal of Algorithms 15 (1993), 199–222; see also older version [1]. ISSN 0196–6774. MR 94m:11148. URL: http://cr.yp.to/

bib/entries.html#1993/bach-cba.

[3] Eric Bach, Jonathan Sorenson, Sieve algorithms for perfect power testing, Algorithmica 9 (1993), 313–328. ISSN 0178–4617. MR 94d:11103.

[4] Daniel J. Bernstein, Detecting perfect powers in essentially linear time, Mathematics of Computation 67 (1998), 1253–1283. ISSN 0025–5718. MR 98j:11121. URL: http://cr.yp.to/

papers.html.

[5] Daniel J. Bernstein, Factoring into coprimes in essentially linear time, to appear, Journal of

Algorithms. ISSN 0196–6774. URL: http://cr.yp.to/papers.html. ID f32943f0bb67a9317d4
021513f9eee5a.

[6] Daniel J. Bernstein, Fast multiplication and its applications, to appear in Buhler-Stevenhagen

Algorithmic number theory book. URL: http://cr.yp.to/papers.html#multapps.

[7] David S. Johnson (editor), Proceedings of the first annual ACM-SIAM symposium on discrete algorithms, January 22–24, 1990, San Francisco, California, Society for Industrial and Applied Mathematics, Philadelphia, 1990. ISBN 0–89871–251–3.

Department of Mathematics, Statistics, and Computer Science (M/C 249), The University of Illinois at Chicago, Chicago, IL 60607–7045, USA

E-mail address: djb@cr.yp.to

Mathematisch Instituut, Universiteit Leiden, Postbus 9512, 2300 RA Leiden, The Netherlands

E-mail address: hwl@math.leidenuniv.nl

Department of Mathematics and Statistics, McGill University, Burnside Hall, Montreal, Quebec, H2A 2K6, Canada

E-mail address: pila@math.mcgill.ca