The crew pram complexity of modular inversion

Joachim Von Zur Gathen; Igor Shparlinski

doi:10.1007/BFb0054331

The crew pram complexity of modular inversion

Joachim Von Zur Gathen, Igor Shparlinski

School of Computing

Research output: Chapter in Book/Report/Conference proceeding › Conference proceeding contribution › peer-review

1 Citation (Scopus)

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.

Original language	English
Title of host publication	LATIN 1998: Theoretical Informatics
Subtitle of host publication	Third Latin American Symposium Campinas, Brazil, April 20–24, 1998 Proceedings
Editors	Cláudio L. Lucchesi, Arnaldo V. Moura
Place of Publication	Berlin; New York
Publisher	Springer, Springer Nature
Pages	305-315
Number of pages	11
ISBN (Electronic)	9783540697152
ISBN (Print)	3540642757, 9783540642756
DOIs	https://doi.org/10.1007/BFb0054331
Publication status	Published - Apr 1998
Event	3rd Latin American Symposium on Theoretical Informatics, LATIN - 1998 - Campinas, Brazil Duration: 20 Apr 1998 → 24 Apr 1998

Publication series

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

Other

Other	3rd Latin American Symposium on Theoretical Informatics, LATIN - 1998
Country/Territory	Brazil
City	Campinas
Period	20/04/98 → 24/04/98

Access to Document

10.1007/BFb0054331

Cite this

Gathen, J. V. Z., & Shparlinski, I. (1998). The crew pram complexity of modular inversion. In C. L. Lucchesi, & A. V. Moura (Eds.), LATIN 1998: Theoretical Informatics: Third Latin American Symposium Campinas, Brazil, April 20–24, 1998 Proceedings (pp. 305-315). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1380). Springer, Springer Nature. https://doi.org/10.1007/BFb0054331

Gathen, Joachim Von Zur ; Shparlinski, Igor. / The crew pram complexity of modular inversion. LATIN 1998: Theoretical Informatics: Third Latin American Symposium Campinas, Brazil, April 20–24, 1998 Proceedings. editor / Cláudio L. Lucchesi ; Arnaldo V. Moura. Berlin; New York : Springer, Springer Nature, 1998. pp. 305-315 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@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 = apr,

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

note = "3rd Latin American Symposium on Theoretical Informatics, LATIN - 1998 ; Conference date: 20-04-1998 Through 24-04-1998",

}

Gathen, JVZ & Shparlinski, I 1998, The crew pram complexity of modular inversion. in CL Lucchesi & AV Moura (eds), LATIN 1998: Theoretical Informatics: Third Latin American Symposium Campinas, Brazil, April 20–24, 1998 Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 1380, Springer, Springer Nature, Berlin; New York, pp. 305-315, 3rd Latin American Symposium on Theoretical Informatics, LATIN - 1998 , Campinas, Brazil, 20/04/98. https://doi.org/10.1007/BFb0054331

The crew pram complexity of modular inversion. / Gathen, Joachim Von Zur; Shparlinski, Igor.
LATIN 1998: Theoretical Informatics: Third Latin American Symposium Campinas, Brazil, April 20–24, 1998 Proceedings. ed. / Cláudio L. Lucchesi; Arnaldo V. Moura. Berlin; New York: Springer, Springer Nature, 1998. p. 305-315 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1380).

Research output: Chapter in Book/Report/Conference proceeding › Conference proceeding contribution › peer-review

TY - GEN

T1 - The crew pram complexity of modular inversion

AU - Gathen, Joachim Von Zur

AU - Shparlinski, Igor

PY - 1998/4

Y1 - 1998/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 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.

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

UR - http://www.scopus.com/inward/record.url?scp=84949211445&partnerID=8YFLogxK

U2 - 10.1007/BFb0054331

DO - 10.1007/BFb0054331

M3 - Conference proceeding contribution

AN - SCOPUS:84949211445

SN - 3540642757

SN - 9783540642756

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 305

EP - 315

BT - LATIN 1998: Theoretical Informatics

A2 - Lucchesi, Cláudio L.

A2 - Moura, Arnaldo V.

PB - Springer, Springer Nature

CY - Berlin; New York

T2 - 3rd Latin American Symposium on Theoretical Informatics, LATIN - 1998

Y2 - 20 April 1998 through 24 April 1998

ER -

Gathen JVZ, Shparlinski I. The crew pram complexity of modular inversion. In Lucchesi CL, Moura AV, editors, LATIN 1998: Theoretical Informatics: Third Latin American Symposium Campinas, Brazil, April 20–24, 1998 Proceedings. Berlin; New York: Springer, Springer Nature. 1998. p. 305-315. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/BFb0054331

The crew pram complexity of modular inversion

Abstract

Publication series

Other

Access to Document

Other files and links

Fingerprint

Cite this