# zbMATH — the first resource for mathematics

Subquadratic-time factoring of polynomials over finite fields. (English) Zbl 0902.11053
Efficiently factoring univariate polynomials over finite fields is a very important step in the solution of many discrete problems. The first random polynomial-time algorithm for such a factorization was given by E. R. Berlekamp [Math. Comput. 24(1970), 713-735 (1971; Zbl 0247.12014)]. About a decade later a very different approach was suggested by D. G. Cantor and H. Zassenhaus [Math. Comput. 36, 587-592 (1981; Zbl 0493.12024)]. In this latter approach the algorithm starts with a polynomial assumed to be square-free, separates the irreducible factors of distinct degrees, and then completely factors each of the resulting factors. A number of other researchers, including both authors, have improved these techniques over the years.
In the paper under review the authors use the basic Cantor/Zassenhaus strategy to develop a probabilistic approach that factors a polynomial of degree $$n$$ over the finite field $$F_q$$ ($$q$$ being held constant) in $$O(n^{1.815})$$ time. This bound is proven by using the result of D. Coppersmith and S. Winograd [J. Symb. Comput. 9, 251-280 (1990; Zbl 0702.65046)] that one can multiply two $$n \times n$$ matrices using only $$O(n^\omega)$$ arithmetic operations, where $$\omega < 2.375477$$. The main technical contribution is a subquadratic distinct-degree factorization algorithm based on the so-called baby step/giant step strategy. The authors also develop a subquadratic algorithm for finding a normal basis of $$F_{q^n}$$ over its subfield $$F_q$$. Since the algorithms discussed rely on fast multiplication of large matrices, as stated they are not particularly practical. However, the techniques can be adapted to give a practical algorithm that seems to factor larger polynomials (in a reasonable amount of time and space) than previously possible. To achieve the subquadratic running time, randomization is of course used. It remains an open problem to find a subquadratic deterministic algorithm.

##### MSC:
 11Y16 Number-theoretic algorithms; complexity 11T06 Polynomials over finite fields 68W30 Symbolic computation and algebraic computation 13P05 Polynomials, factorization in commutative rings 12E20 Finite fields (field-theoretic aspects) 12Y05 Computational aspects of field theory and polynomials (MSC2010)
Full Text: