@inproceedings{757e2725633f4a51a166d615fcebbd2d,

title = "The crew pram complexity of modular inversion",

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 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.",

author = "Gathen, {Joachim Von Zur} and Igor Shparlinski",

year = "1998",

month = "4",

doi = "10.1007/BFb0054331",

language = "English",

isbn = "3540642757",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer, Springer Nature",

pages = "305--315",

editor = "Lucchesi, {Cl{\'a}udio L.} and Moura, {Arnaldo V.}",

booktitle = "LATIN 1998: Theoretical Informatics",

address = "United States",

}