How fast can we compute the roots of a polynomial over a large finite field?
Michael Monagan, Department of Mathematics, Simon Fraser University
Mahdi Javadi and I have developed a parallel algorithm for sparse polynomial interpolation over large finite fields. The bottleneck of the algorithm is polynomial root finding over a finite field. This talk considers the problem of computing roots of polynomials over finite fields. Suppose we are given a polynomial f(x) of degree d over a finite field GF(q), q odd. In 1980 Rabin presented a probabilistic algorithm which computes the roots of f(x) in GF(q). When q is large, computation of the remainder of (x+alpha)^(q-1)/2 divided b(x) of degree n dominates the cost of the algorithm. This power mod b(x) is computed with the square-and-multiply algorithm. For n also large, fast polynomial arithmetic multiplication can be used so that the remainder r(x) can be computed in O( log p M(n) ) where M(n) is the number of arithmetic operations in GF(q) for one multiplication of degree n. If the FFT is used then M(n) is in O( n log n log log n ). When one implements a fast algorithm, one does care about the constant. Thus instead of just focussing on the asymptotic behaviour of the algorithm, and counting the number of multiplications of degree n that it does, we count the number of FFTs of size n that it does. We show, in successive improvements how to reduce this number from 17 to 8 to 6 to 4 to 2. For the latter two improvements, instead of computing with polynomials, we compute in Fourier transform co-ordinates, leaving them only when necessary.