Home
Search Site
Largest
Finding
How Many?
Mersenne
Glossary
Prime Curios!
email list
FAQ
Prime Lists
Titans
Submit primes

This is the Prime Pages'
interface to our BibTeX database. Rather than being an exhaustive database,
it just lists the references we cite on these pages. Please let me know of any errors you notice.References: [ Home  Author index  Key index  Search ]
 Bernstein1998b
 D. Berstein, "Detecting perfect powers in essentially linear time," Math. Comp., 67:223 (1998) 12531283. Available from http://cr.yp.to/papers.html. MR 98j:11121
Abstract:
This paper (1) gives complete details of an algorithm to compute approximate kth roots; (2) uses this in an algorithm that, given an integer n>1, either writes n as a perfect power or proves that n is not a perfect power; (3) proves, using Loxton's theorem on multiple linear forms in logarithms, that this perfectpower decomposition algorithm runs in time (log n)^{1+o(1)}.
