CREW PRAM complexity of modular inversion

Joachim Von Zur Gathen; Igor E. Shparlinski

doi:10.1137/S0097539797328070

CREW PRAM complexity of modular inversion

Joachim Von Zur Gathen, Igor E. Shparlinski

School of Computing

Research output: Contribution to journal › Article › peer-review

1 Citation (Scopus)

26 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 language	English
Pages (from-to)	1839-1857
Number of pages	19
Journal	SIAM Journal on Computing
Volume	29
Issue number	6
DOIs	https://doi.org/10.1137/S0097539797328070
Publication status	Published - 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/.

Access to Document

10.1137/S0097539797328070

Publisher version (open access).pdfFinal published version, 196 KB

Cite this

@article{3678195137b948e3ab82bd50d662b45b,

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

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

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

year = "2000",

month = apr,

doi = "10.1137/S0097539797328070",

language = "English",

volume = "29",

pages = "1839--1857",

journal = "SIAM Journal on Computing",

issn = "0097-5397",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "6",

}

TY - JOUR

T1 - CREW PRAM complexity of modular inversion

AU - Von Zur Gathen, Joachim

AU - Shparlinski, Igor E.

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

PY - 2000/4

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

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

UR - https://www.scopus.com/pages/publications/0034476438

U2 - 10.1137/S0097539797328070

DO - 10.1137/S0097539797328070

M3 - Article

AN - SCOPUS:0034476438

SN - 0097-5397

VL - 29

SP - 1839

EP - 1857

JO - SIAM Journal on Computing

JF - SIAM Journal on Computing

IS - 6

ER -

CREW PRAM complexity of modular inversion

Abstract

Bibliographical note

Access to Document

Other files and links

Fingerprint

Cite this