Detecting perfect powers by factoring into coprimes
This paper presents an algorithm that, given an integer n > 1, finds the largest integer k such that n is a kth power. A previous algorithm by the first author took time b1+o(1) where b = lg n; more precisely, time b exp(O(√lg b lg lg b)); conjecturally, time b(lg b)O(1) The new algorithm tak...
| Main Authors: | , , |
|---|---|
| 格式: | Journal article |
| 语言: | English |
| 出版: |
American Mathematical Society
2006
|