The crew pram complexity of modular inversion

Joachim Von Zur Gathen, Igor Shparlinski

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contribution

1 Citation (Scopus)


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 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 for exponential sums in finite fields.

Original languageEnglish
Title of host publicationLATIN 1998: Theoretical Informatics
Subtitle of host publicationThird Latin American Symposium Campinas, Brazil, April 20–24, 1998 Proceedings
EditorsCláudio L. Lucchesi, Arnaldo V. Moura
Place of PublicationBerlin; New York
PublisherSpringer, Springer Nature
Number of pages11
ISBN (Electronic)9783540697152
ISBN (Print)3540642757, 9783540642756
Publication statusPublished - Apr 1998
Event3rd Latin American Symposium on Theoretical Informatics, LATIN - 1998 - Campinas, Brazil
Duration: 20 Apr 199824 Apr 1998

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)03029743
ISSN (Electronic)16113349


Other3rd Latin American Symposium on Theoretical Informatics, LATIN - 1998

Fingerprint Dive into the research topics of 'The crew pram complexity of modular inversion'. Together they form a unique fingerprint.

Cite this