Polylog Depth Circuits for Integer Factoring and Discrete Logarithms

AbstractIn this paper, we develop parallel algorithms for integer factoring and for computing discrete logarithms. In particular, we give polylog depth probabilistic boolean circuits of subexponential size for both of these problems, thereby solving an open problem of Adleman and Kompella. Existing sequential algorithms for integer factoring and discrete logarithms use a prime base which is the set of all primes up to a bound B. We use a much smaller value for B for our parallel algorithms than is typical for sequential algorithms. In particular, for inputs of length n, by setting B = nlogdn with d a positive constant, we construct •Probabilistic boolean circuits of depth (log) and size exp[(/log)] for completely factoring a positive integer with probability 1−(1), and•Probabilistic boolean circuits of depth (log + log) and size exp[(/log)] for computing discrete logarithms in the finite field () for a prime with probability 1−(1). These are the first results of this type for both problems