Balasubramanian, R. ; Nagaraj, S. V. (1996) Perfect power testing Information Processing Letters, 58 (2). pp. 59-63. ISSN 0020-0190
Full text not available from this repository.
Official URL: http://www.sciencedirect.com/science/article/pii/0...
Related URL: http://dx.doi.org/10.1016/0020-0190(96)00042-7
Abstract
Bach and Sorenson present two algorithms for testing whether a number n is a perfect power, with average running time O(log2n) under the assumption that n is chosen uniformly from an interval of length at least (logn)3 logloglogn.We modify their algorithms to reduce the interval to polynomial size.
| Item Type: | Article |
|---|---|
| Source: | Copyright of this article belongs to Elsevier Science. |
| Keywords: | Analysis of Algorithms; Perfect Powers; Number Theoretic Algorithms |
| ID Code: | 72409 |
| Deposited On: | 29 Nov 2011 12:42 |
| Last Modified: | 29 Nov 2011 12:42 |
Repository Staff Only: item control page
