Perfect power testing

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