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...
| Главные авторы: | , , |
|---|---|
| Формат: | Journal article |
| Язык: | English |
| Опубликовано: |
American Mathematical Society
2006
|