On the Time Required to Perform Addition

Abstract

The time required to perform a group operation using logical circuitry is investigated. A lower bound on this time is derived, and in the ease that the group is abelian it is shown that the lower bound can be approached as the complexity of the elements used i~ereases. In particular, if the group operation is adding integers modulo t~, it, is shown that the lower bound behaves as log log a(t~), where a(,) is the largest power of a prime which divides ~.