Detecting perfect powers by factoring into coprimes

D.J. Bernstein, H.W. Lenstra, J. Pila

    Research output: Contribution to journalArticlepeer-review

    10 Citations (Scopus)
    2 Downloads (Pure)

    Abstract

    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.
    Original languageEnglish
    Pages (from-to)385-388
    JournalMathematics of Computation
    Volume76
    DOIs
    Publication statusPublished - 2007

    Fingerprint

    Dive into the research topics of 'Detecting perfect powers by factoring into coprimes'. Together they form a unique fingerprint.

    Cite this