Energy Citations Database

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 Date1988 Jul 01
OSTI IdentifierOSTI ID: 6508774
Other Number(s)CODEN: JACOA
Resource TypeJournal Article
Resource RelationJ. Assoc. Comput. Mach. ; Vol/Issue: 31:9
Subject990210 -- Supercomputers-- (1987-1989); PARALLEL PROCESSING-- TECHNOLOGY ASSESSMENT; COMPUTER CALCULATIONS;POLYNOMIALS
Related SubjectFUNCTIONS;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 PublicationUnited States
LanguageEnglish
FormatPages: 1143
System Entry Date2001 May 13

Top