• TUCS Publication Series
• How to Publish in TUCS Series
• Publication Search
• Publication Graph
• Publication Input
• Publication Input Guide
• JuFo Browser

Computing Partial Information out of Intractable: Powers of Algebraic Numbers as an Example

Mika Hirvensalo, Juhani Karhumäki, Alexander Rabinovich, Computing Partial Information out of Intractable: Powers of Algebraic Numbers as an Example. Journal of Number Theory 130(2), 232–253 , 2010.

http://dx.doi.org/10.1016/j.jnt.2009.08.009

Abstract:

We consider an algorithmic problem of computing the first, i.e., the most significant digits of n2 (in base 3) and of the nth Fibonacci number. While the decidability is trivial, efficient algorithms for those problems are not immediate. We show, based on Baker's inapproximability results of transcendental numbers that both of the above problems can be solved in polynomial time with respect to the length of n. We point out that our approach works also for much more general expressions of algebraic numbers.

BibTeX entry:

@ARTICLE{jHiKaRa10a,
  title = {Computing Partial Information out of Intractable: Powers of Algebraic Numbers as an Example},
  author = {Hirvensalo, Mika and Karhumäki, Juhani and Rabinovich, Alexander},
  journal = {Journal of Number Theory},
  volume = {130},
  number = {2},
  pages = {232–253 },
  year = {2010},
}

Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics

Publication Forum rating of this publication: level 2

Edit publication