Parallel complexity of integer coprimality
Bruce E. Litow · 1998
It is shown that integer coprimality testing is in NC. AMS classification codes: 68Q15, 68Q22, 68Q25 1 Introduction The object of this paper is to prove Theorem 1 Integer coprimality is in NC. 1.1 Background The parallel complexity of basic arithmetic operations has been closely investigated since the 1960's. In the case of arithmetic, problem size is usually measured in terms of binary notation for the integer inputs. It is known that addition and multiplication of n-bit integers can be done in NC1, i.e., by logspace computable Boolean circuit families of O(log n) depth and with n O(1) Boolean gates. Details about these classical results may be found in [12], and information about the parallel complexity class NC may be found in [11, 4]. It is also know that division can be done in the same time and size bounds, but slightly more than logspace is needed to build the requisite Boolean circuits. It is open whether or not division is in NC1. See [2, 5, 7] for more information abou...