On the Efficiency of Algorithms for Polynomial Factoring

Abstract

Algorithms for factoring polynomials over finite fields are discussed. A construction is shown which reduces the final step of Berlekamp’s algorithm to the problem of finding the roots of a polynomial in a finite field ${Z_p}$. It is shown that if the characteristic of the field is of the form $p = L \cdot {2^l} + 1$, where $l \simeq L$, then the roots of a polynomial of degree n may be found in $O({n^2}\log p + n{\log ^2}p)$ steps. As a result, a modification of Berlekamp’s method can be performed in $O({n^3} + {n^2}\log p + n{\log ^2}p)$ steps. If n is very large then an alternative method finds the factors of the polynomial in $O({n^2}{\log ^2}n + {n^2}\log n\log p)$. Some consequences and empirical evidence are discussed.