The parallel complexity of exponentiating polynomials over finite fields

Publisher Website
Google Scholar
Abstract
Modular integer exponentiation (given a, e, and m , compute a 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 )) e mod m ( x )) and polynomial exponentiation (given a ( x ), e . and t , compute the coefficient of x t in ( a ( x )) e ). It is shown that these latter two problems are in NC 2 when a ( x ) and m ( x ) are polynomials over a finite field whose characteristic is polynomial in the input size.

This publication has 10 references indexed in Scilit: