POLYLOG DEPTH CIRCUITS FOR INTEGER FACTORING AND DISCRETE LOGARITHMS

In this paper, we develop parallel algorithms for integer factoring an d for computing discrete logarithms. In particular, we give polylog de pth probabilistic boolean circuits of subexponential size for both of these problems, thereby solving an open problem of Adleman and Kompell a. Existing sequential algorithms for integer factoring and discrete l ogarithms use a prime have which is the set of all primes up to a boun d B. We use a much smaller value for B for our parallel algorithms tha n is typical for sequential algorithms, In particular, for inputs of l ength n, by setting B = n(logdn) with d a positive constant, we constr uct Probabilistic boolean circuits of depth O(log2d+2n) and size exp[O (n/log(d)n)] for completely factoring a positive integer with probabil ity 1 - o(1), and Probabilistic boolean circuits of depth O(log2d+2 n + log3n) and size exp[O(n/log(d)n)] for computing discrete logarithms in the finite field GF(p) for p a prime with probability 1 - o(1). The se are the first results of this type for both problems. (C) 1994 Acad emic Press, inc.