Arithmetic complexity

Lou Van Den Dries, Yiannis N. Moschovakis

Research output: Contribution to journalArticlepeer-review


We obtain lower bounds on the cost of computing various arithmetic functions and deciding various arithmetic relations from specified primitives. This includes lower bounds for computing the greatest common divisor and deciding coprimeness of two integers, from primitives like addition, subtraction, division with remainder and multiplication. Some of our results are in terms of recursive programs, but they generalize directly to most (plausibly all) algorithms from the specified primitives. Our methods involve some elementary number theory as well as the development of some basic notions and facts about recursive algorithms.

Original languageEnglish (US)
Article number2
JournalACM Transactions on Computational Logic
Issue number1
StatePublished - Nov 1 2008


  • Coprimeness
  • Greatest common divisor
  • Lower bounds for arithmetical problems
  • Recursive programs

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science
  • Logic
  • Computational Mathematics


Dive into the research topics of 'Arithmetic complexity'. Together they form a unique fingerprint.

Cite this