Detecting perfect powers in essentially linear time
Open Access
- 1 July 1998
- journal article
- research article
- Published by American Mathematical Society (AMS) in Mathematics of Computation
- Vol. 67 (223) , 1253-1283
Abstract
This paper (1) gives complete details of an algorithm to compute approximate k k th roots; (2) uses this in an algorithm that, given an integer n > 1 n>1 , either writes n n as a perfect power or proves that n n 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 ( log n ) 1 + o ( 1 ) (\log n)^{1+o(1)} .Keywords
This publication has 18 references indexed in Scilit:
- Pi and the AGM, by Jonathan M. Borwein and Peter B. Borwein. Pp. 414. £38.95. 1998. ISBN 0 471 31515 X (Wiley Interscience).The Mathematical Gazette, 1999
- A hyperelliptic smoothness test. IPhilosophical Transactions A, 1993
- Sieve algorithms for perfect power testingAlgorithmica, 1993
- A Course in Computational Algebraic Number Theory1993
- Matrix Analysis1985
- Fast compact prime number sieves (among others)Journal of Algorithms, 1983
- On a problem of Oppenheim concerning “factorisatio numerorum”Journal of Number Theory, 1983
- Fast polynomial transform algorithms for digital convolutionIEEE Transactions on Acoustics, Speech, and Signal Processing, 1980
- Fast Multiple-Precision Evaluation of Elementary FunctionsJournal of the ACM, 1976
- Schnelle Multiplikation großer ZahlenComputing, 1971