Factoring multivariate polynomials over large finite fields

Abstract:

A simple probabilistic algorithm is presented to find the irreducible factors of a bivariate polynomial over a large finite field. For a polynomial $f(x,y)$ over ${F_q}$ of total degree n, our algorithm takes at most \[ {n^{4.89}}{\log ^2}n\log q\] operations in ${F_q}$ to factor $f(x,y)$ completely. This improves a probabilistic factorization algorithm of von zur Gathen and Kaltofen, which takes \[ O({n^{11}}\log n\log q)\] operations to factor $f(x,y)$ completely over ${F_q}$. The algorithm can be easily generalized to factor multivariate polynomials over finite fields. We shall give two further applications of the idea involved in the algorithm. One is concerned with exponential sums; the other is related to permutational polynomials over finite fields (a conjecture of Chowla and Zassenhaus).