Mark Lavin

Works (1)

Updated: July 5th, 2023 15:48

2010 journal article

Efficiently Certifying Non-Integer Powers

COMPUTATIONAL COMPLEXITY, 19(3), 355–366.

By: E. Kaltofen n & M. Lavin n

author keywords: Integer roots; integer powers; linear-time algorithm; bit complexity; Chebotarev density theorem
TL;DR: A randomized algorithm that, given an integer a, produces a certificate that the integer is not a pure power of an integer in expected (log a)1+o(1) bit operations under the assumption of the Generalized Riemann Hypothesis is described. (via Semantic Scholar)
Source: Web Of Science
Added: August 6, 2018

Citation Index includes data from a number of different sources. If you have questions about the sources of data in the Citation Index or need a set of data which is free to re-distribute, please contact us.

Certain data included herein are derived from the Web of Science© and InCites© (2025) of Clarivate Analytics. All rights reserved. You may not copy or re-distribute this material in whole or in part without the prior written consent of Clarivate Analytics.