Detecting perfect powers by factoring into coprimes

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

    Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

    10 Citaten (Scopus)
    2 Downloads (Pure)


    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.
    Originele taal-2Engels
    Pagina's (van-tot)385-388
    TijdschriftMathematics of Computation
    StatusGepubliceerd - 2007


    Duik in de onderzoeksthema's van 'Detecting perfect powers by factoring into coprimes'. Samen vormen ze een unieke vingerafdruk.

    Citeer dit