The essential idea in the fast parallel computation of division and
related problems is that of Chinese remainder representation
(CRR) -- storing a number in the form of its residues modulo many
small primes. Integer division provides one of the few natural
examples of problems for which all currently-known constructions of
efficient circuits rely on some sort of extra information or
non-uniformity; the major stumbling block has seemed to be the
difficulty of converting from CRR to binary. We give new bounds on
the nonuniformity required for division; it is necessary and
sufficient to be able to compute discrete logarithms modulo an
O(log n) bit number. In particular, we show that the necessary
uniformity predicates lie in a class that (provably) does not
contain L.
The fact that CRR operations can be carried out in log space has
interesting implications for small space classes. We define two
versions of s(n) space for s(n)=o(log n): dspace(s(n)) as the
traditional version where the worktape begins blank, and DSPACE(s(n))
where the space bound is established by endmarkers before the
computation starts. We present a new translational lemma, and
derive as a consequence that (for example), if one can improve the
result of [Hartmanis,Berman] that {0^n : n is prime} is not in
dspace(loglog n) to show that {0^n : n is prime} is not in
DSPACE(loglog n), it would follow that L is not equal to NP.
The MS thesis of Andrew Chiu:
("Complexity of Parallel Arithmetic Using the
Chinese Remainder Representation"
University of Wisconsin-Milwaukee, August, 1995)
contains an algorithm for integer division, that
can be implemented in Atime(log n) (i.e., in the
most uniform version of NC^1). Our ECCC Submission
will be revised soon, to reflect this.
This paper became obsolete shortly after it appeared in ECCC.
A new paper (with William Hesse as co-author) is now available
as ECCC report TR01-033.
