# best deterministic complexity for factoring polynomials over finite field

I would like to know currently what's the best deterministic complexity for factoring polynomials over finite field (without the assumption of GRH)? I have searched on google, there are many source, but I can't find an explicit result. Some of them are only for some special cases. Some of them are used the assumption of GRH.

• The trouble is that different algorithms have different complexities in different situations. The situation changes drastically from polynomials of large degree over small finite fields (where Berlekamp's algorithm is polynomial time) to quadratic polynomials over large prime fields (where deteministically you are stuck with dumb potentially exponential time algorithms). – Felipe Voloch Apr 7 '11 at 0:02

First, let me echo Felipe Voloch's comment and the answer by (the other) unknown (google). Having done that, here are a few recent papers that might be of interest.

Mullin, Ronald C.; Yucas, Joseph L.; Mullen, Gary L., A generalized counting and factoring method for polynomials over finite fields. J. Combin. Math. Combin. Comput. 72 (2010), 121–143. No review yet, so I don't know what's in there.

You don't say how many variables your polynomials have. If it's two, then the review of MR2537701 (2010d:12001) Belabas, Karim; van Hoeij, Mark; Klüners, Jürgen; Steel, Allan, Factoring polynomials over global fields. J. Théor. Nombres Bordeaux 21 (2009), no. 1, 15–39 by R. A. Mollin says, "They also provide polynomial time complexity results for bivariate polynomials over a finite field."

I was going to mention MR2582906 (2011c:68221) Umans, Christopher, Fast polynomial factorization and modular composition in small characteristic. STOC'08, 481–490, ACM, New York, 2008, but then I noticed the summary says "We obtain randomized algorithms for factoring degree $n$ univariate polynomials over $F_q$ that use $O(n^{1.5+o(1)}+n^{1+o(1)}\log q)$ field operations, when the characteristic is at most $n^{o(1)}$," and you don't want randomized algorithms, right?

MR2284290 (2007m:68318) Genovese, Giulio, Improving the algorithms of Berlekamp and Niederreiter for factoring polynomials over finite fields. J. Symbolic Comput. 42 (2007), no. 1-2, 159–177 claims "to accelerate deterministic algorithms for the factorization of polynomials over finite fields."

A deterministic algorithm of Shoup factors univariate polynomials of degree $n$ over $Z/pZ$ in time (worst case) $$O(p^{1/2}n^{2 + \varepsilon} (\log p)^2)$$

Regarding 'best known' I cannot say anything; but since you said you had no explicit result I thought it might still be useful information.

Check the recent paper by Bourgain, Konyagin and Shparlinski: CHARACTER SUMS AND DETERMINISTIC POLYNOMIAL ROOT FINDING IN FINITE FIELDS

• Nice reference (though only does a special case...) – Igor Rivin Oct 18 '16 at 12:28