On the Time Required to Perform Addition
Shmuel Winograd · Journal of the ACM · 1965
4bslracl.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 ~.