The parallel complexity of exponentiating polynomials over finite fields

Reviewer: Hale F. Trotter

This paper considers the complexity of parallel computation for modular polynomial exponentiation and polynomial exponentiation: that is, given polynomials a( x) and m( x) over a finite field F, and positive integers e and t, compute a( x) e mod m( x) and m( x) and the coefficient of x t in a( x) e, respectively. The input size of a problem is defined as the maximum of the degrees of a( x) and the number of bits in e. Fitch and Tompa present algorithms for both problems that show them to be in the complexity class NC 2 when the characteristic of F is polynomial in the input size. Note that the restriction on F refers to its characteristic, not its order. Both algorithms use the relation a( x) q = a( x q), where q is the order of F, and break the computation up into pieces corresponding to the digits in the base q representation of e. Raising to the qth power in the modular algorithm is then equivalent to matrix multiplication (as in Berlekamp's factorization algorithm), and operations on different rows can be done in parallel. For the second problem, a( x) e becomes a product of sparse polynomials with rather special structure, and the authors show that the coefficient of x t can be found by a combinatorial calculation that admits parallel computation. The authors provide some background discussion, including a comparison of these results with those for related problems. I recommend the paper to those interested in the subject.