One of the long-standing open questions in the theory of parallel computation is the parallel compelxity of the integer gcd and related problems, such as modular inversion. We present a lower bound omiga(log n) for the CREW PRAM complexity for inversion modulo certain n-bit integers, including all such primes. For infinitely many moduli, our lower bound matches asymptotically the known upper bound. We obtain a similar lower bound for computing a specified bit in a large power of an integer. Our main tools are certain estimates exponential sums in finite fields.
展开▼
