Subquadratic-time factoring of polynomials over finite fields
Open Access
- 1 July 1998
- journal article
- Published by American Mathematical Society (AMS) in Mathematics of Computation
- Vol. 67 (223) , 1179-1197
Abstract
New probabilistic algorithms are presented for factoring univariate polynomials over finite fields. The algorithms factor a polynomial of degree n n over a finite field of constant cardinality in time O ( n 1.815 ) O(n^{1.815}) . Previous algorithms required time Θ ( n 2 + o ( 1 ) ) \Theta (n^{2+o(1)}) . The new algorithms rely on fast matrix multiplication techniques. More generally, to factor a polynomial of degree n n over the finite field F q {\mathbb F}_q with q q elements, the algorithms use O ( n 1.815 log q ) O(n^{1.815} \log q) arithmetic operations in F q {\mathbb F}_q . The new “baby step/giant step” techniques used in our algorithms also yield new fast practical algorithms at super-quadratic asymptotic running time, and subquadratic-time methods for manipulating normal bases of finite fields.Keywords
This publication has 35 references indexed in Scilit:
- A new efficient factorization algorithm for polynomials over small finite fieldsApplicable Algebra in Engineering, Communication and Computing, 1993
- Computing Frobenius maps and factoring polynomialscomputational complexity, 1992
- On fast multiplication of polynomials over arbitrary algebrasActa Informatica, 1991
- Addition requirements for matrix and transposed matrix productsJournal of Algorithms, 1988
- On the equivalence between Berlekamp's and Euclid's algorithms (Corresp.)IEEE Transactions on Information Theory, 1987
- A New Algorithm for Factoring Polynomials Over Finite FieldsMathematics of Computation, 1981
- Fast solution of toeplitz systems of equations and computation of Padé approximantsJournal of Algorithms, 1980
- Taylor expansion of the accumulated rounding errorBIT Numerical Mathematics, 1976
- Shift-register synthesis and BCH decodingIEEE Transactions on Information Theory, 1969
- ON THE REDUCTIBILITY OF POLYNOMIALS OVER A FINITE FIELDThe Quarterly Journal of Mathematics, 1956