1
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • 3
    $\begingroup$ 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). $\endgroup$
    – Felipe Voloch
    Commented Apr 7, 2011 at 0:02

3 Answers 3

Reset to default
3
$\begingroup$

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

Improve this answer
$\endgroup$
4
$\begingroup$

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.

Improve this answer
$\endgroup$
2
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ Nice reference (though only does a special case...) $\endgroup$
    – Igor Rivin
    Commented Oct 18, 2016 at 12:28

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .