Computing partial information out of intractable: powers of algebraic numbers as an example
type: Item
instance of: scholarly article
title: Computing partial information out of intractable: powers of algebraic numbers as an example
zbMATH Open document ID: 1251.11052
author: Mika Hirvensalo
author: Juhani Karhumäki
author: Alexander Rabinovich
published in: Journal of Number Theory
publication date: 2010-01-08T00:00:00Z
review text: The paper contains efficient algorithms for computing the leftmost digit in base 3 of the numbers \(2^n\) and the Fibonacci number \(F_n\). Using Baker's estimates on linear forms in logarithms, the authors prove that these two problems can be solved in polynomial time with respect to the length of \(n\).
reviewed by: Maurice Mignotte
Mathematics Subject Classification ID: 11J86
Mathematics Subject Classification ID: 11J68
Mathematics Subject Classification ID: 11Y16
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 5654993
zbMATH Keywords: efficient computability
zbMATH Keywords: Baker theory
MaRDI profile type: Publication
full work available at URL: j.jnt.2009.08.009
OpenAlex ID: W2081664556
cites work: Q4050665
cites work: Q4134062
cites work: Q3960783
cites work: Q3261425
cites work: Q3715120
cites work: Q4708580
cites work: Q4771385
cites work: Q5647003
cites work: Q3963114
cites work: Q3768984
DOI: 10.1016/J.JNT.2009.08.009
description: scientific article; zbMATH DE number 5654993