TY - JOUR
T1 - CREW PRAM complexity of modular inversion
AU - Von Zur Gathen, Joachim
AU - Shparlinski, Igor E.
N1 - Copyright SIAM Publications. Article archived for private and non-commercial use with the permission of the author and according to publisher conditions. For further information see http://www.siam.org/.
PY - 2000/4
Y1 - 2000/4
N2 - One of the long-standing open questions in the theory of parallel computation is the parallel complexity of the integer gcd and related problems, such as modular inversion. We present a lower bound Ω(log n) for the parallel time on a concurrent-read exclusive-write parallel random access machine (CREW PRAM) computing the inverse 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 for exponential sums in finite fields.
AB - One of the long-standing open questions in the theory of parallel computation is the parallel complexity of the integer gcd and related problems, such as modular inversion. We present a lower bound Ω(log n) for the parallel time on a concurrent-read exclusive-write parallel random access machine (CREW PRAM) computing the inverse 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 for exponential sums in finite fields.
UR - http://www.scopus.com/inward/record.url?scp=0034476438&partnerID=8YFLogxK
U2 - 10.1137/S0097539797328070
DO - 10.1137/S0097539797328070
M3 - Article
AN - SCOPUS:0034476438
SN - 0097-5397
VL - 29
SP - 1839
EP - 1857
JO - SIAM Journal on Computing
JF - SIAM Journal on Computing
IS - 6
ER -