CREW PRAM complexity of modular inversion

Joachim Von Zur Gathen, Igor E. Shparlinski

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)
9 Downloads (Pure)

Abstract

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
Volume29
Issue number6
DOIs
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 http://www.siam.org/.

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

Cite this