Detecting perfect powers in essentially linear time

D.J. Bernstein

    Research output: Contribution to journalArticleAcademicpeer-review

    27 Citations (Scopus)
    2 Downloads (Pure)

    Abstract

    This paper (1) gives complete details of an algorithm to compute approximate th roots; (2) uses this in an algorithm that, given an integer , either writes as a perfect power or proves that is not a perfect power; (3) proves, using Loxton's theorem on multiple linear forms in logarithms, that this perfect-power decomposition algorithm runs in time (logn)1+0(1).
    Original languageEnglish
    Pages (from-to)1253-1283
    Number of pages31
    JournalMathematics of Computation
    Volume67
    Issue number223
    DOIs
    Publication statusPublished - 1998

    Fingerprint

    Dive into the research topics of 'Detecting perfect powers in essentially linear time'. Together they form a unique fingerprint.

    Cite this