On the efficiency of algorithms for polynomial factoring
Robert T. Moenck · Mathematics of Computation · 1977
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 {Z_p} . It is shown that if the characteristic of the field is of the form p = L ⋅ 2 l + 1 p = L \cdot {2^l} + 1 , where l ≃ L 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 ) 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 ) 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 ) O({n^2}{\log ^2}n + {n^2}\log n\log p) . Some consequences and empirical evidence are discussed.