TY - JOUR

T1 - Detecting perfect powers by factoring into coprimes

AU - Bernstein, D.J.

AU - Lenstra, H.W.

AU - Pila, J.

PY - 2007

Y1 - 2007

N2 - This paper presents an algorithm that, given an integer , finds the largest integer such that is a th power. A previous algorithm by the first author took time where ; more precisely, time ; conjecturally, time . The new algorithm takes time . 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 bound without much background; the previous proof of relied on transcendental number theory.
The computation of is the first step, and occasionally the bottleneck, in many number-theoretic algorithms: the Agrawal-Kayal-Saxena primality test, for example, and the number-field sieve for integer factorization.

AB - This paper presents an algorithm that, given an integer , finds the largest integer such that is a th power. A previous algorithm by the first author took time where ; more precisely, time ; conjecturally, time . The new algorithm takes time . 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 bound without much background; the previous proof of relied on transcendental number theory.
The computation of is the first step, and occasionally the bottleneck, in many number-theoretic algorithms: the Agrawal-Kayal-Saxena primality test, for example, and the number-field sieve for integer factorization.

U2 - 10.1090/S0025-5718-06-01837-0

DO - 10.1090/S0025-5718-06-01837-0

M3 - Article

SN - 0025-5718

VL - 76

SP - 385

EP - 388

JO - Mathematics of Computation

JF - Mathematics of Computation

ER -