CREW PRAM complexity of modular inversion

Joachim Von Zur Gathen, Igor E. Shparlinski

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)
8 Downloads (Pure)


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.

Original languageEnglish
Pages (from-to)1839-1857
Number of pages19
JournalSIAM Journal on Computing
Issue number6
Publication statusPublished - Apr 2000

Bibliographical note

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


Dive into the research topics of 'CREW PRAM complexity of modular inversion'. Together they form a unique fingerprint.

Cite this