MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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
up vote 3 down vote accepted

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."

share|cite|improve this answer

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)$$

On the deterministic complexity of factoring polynomials over finite fields, Information Processing Letters 33:261-267, 1990

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.