On the Efficiency of Algorithms for Polynomial Factoring
Author:
- Robert T. MoenckRMRobert T. Moenck
- 1 January 1977
- journal article
- Published by JSTOR in Mathematics of Computation
- Vol. 31 (137) , 235-250
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.
Keywords
This publication has 7 references indexed in Scilit:
- The Calculation of Multivariate Polynomial ResultantsJournal of the ACM, 1971
- Factoring Polynomials Over Large Finite FieldsMathematics of Computation, 1970
- The Art of Computer Programming. Vol. II: Seminumerical AlgorithmsMathematics of Computation, 1970
- Gaussian elimination is not optimalNumerische Mathematik, 1969
- Computing Multiplicative Inverses in GF(p)Mathematics of Computation, 1969
- Symbolic factoring of polynomials in several variablesCommunications of the ACM, 1966
- Fundamental Concepts of Higher Algebra.The American Mathematical Monthly, 1957