About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
Journal of the ACM
Paper
The parallel complexity of exponentiating polynomials over finite fields
Abstract
Modular integer exponentiation (given a, e, and m, compute ae 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))e mod m(x)) and polynomial exponentiation (given a(x), e. and t, compute the coefficient of xt in (a(x))e). It is shown that these latter two problems are in NC2 when a(x) and m(x) are polynomials over a finite field whose characteristic is polynomial in the input size. © 1988, ACM. All rights reserved.