Bibliographic Citation
Document | For copies of Journal Articles, please contact the Publisher or your local public or university library and refer to the information in the Resource Relation field. For copies of other documents, please see the Availability, Publisher, Research Organization, Resource Relation and/or Author (affiliation information) fields and/or Document Availability. |
---|---|
Title | The parallel complexity of exponentiating polynomials over finite fields |
Creator/Author | Fich, F.E. ; Tompa, M. (Dept. of Computer Science, Univ. of Toronto, Toronto, Ontario M5S 1A4 (CA)) |
Publication Date | 1988 Jul 01 |
OSTI Identifier | OSTI ID: 6508774 |
Other Number(s) | CODEN: JACOA |
Resource Type | Journal Article |
Resource Relation | J. Assoc. Comput. Mach. ; Vol/Issue: 31:9 |
Subject | 990210 -- Supercomputers-- (1987-1989); PARALLEL PROCESSING-- TECHNOLOGY ASSESSMENT; COMPUTER CALCULATIONS;POLYNOMIALS |
Related Subject | FUNCTIONS;PROGRAMMING |
Description/Abstract | Modular integer exponentiation (given a, e, and M, compute a/sup e/ mod m) is a fundamental problem in algebraic complexity for which no efficient parallel algorithm is known.^Two closely related problems are modular polynomial exponentiation (given a(x), e, and (m(x), compute (a(x))/sup e/ mod m(x)) and polynomial exponentiation (given a(x), e and t compute the coefficient of x/sup t/ in (a(x))/sup e/).^It is shown that these latter two problems are in NC/sup 2/ when a(x) and m(x) are polynomials over a finite field whose characteristic is polynomial in the input size. |
Country of Publication | United States |
Language | English |
Format | Pages: 1143 |
System Entry Date | 2001 May 13 |
Top |