# Polynomial factoring over finite fields

What is known in general about the complexity of factoring polynomials over finite fields?

For instance given $\Bbb F_q$ where $q=p^n$ and total degree $d$ polynomial in $m$ variables what can we say about the complexity of factoring polynomials over $\Bbb F_q[x_1,\dots,x_m]$? In general is there a class of polynomials whose factoring is $NP$-hard or $coNP$-hard?

Is there a good reference to understand the topic well?

• The Cantor-Zassenhaus algorithm is commonly used. en.wikipedia.org/wiki/Cantor%E2%80%93Zassenhaus_algorithm Jan 24 '16 at 23:51
• For complexity of the C-Z algorithm see Theorem 5 on page 20 of digitalcommons.uconn.edu/cgi/… for its complexity (and perhaps Chapter 6 of amazon.com/Algebraic-Coding-Theory-Revised-Edition/dp/… gives further information). Jan 24 '16 at 23:53
• The above are for 1-variable polynomials over finite fields. For $m>1$ variables is it comparable in difficulty to factoring polynomials in $m-1$ variables over $\mathbf{Z}$? Jan 25 '16 at 0:08
• @nfdc23 Good problem do not know.
– user76479
Jan 25 '16 at 0:11

For dense univariate polynomials, the state of the art is due to Kedlaya and Umans (Fast polynomial factorization and modular composition, SIAM J. Comput. 40 (2011), 1767–1802). They obtain randomized algorithms for factoring degree $n$ univariate polynomials over $\mathbb{F}_q$ requiring $O(n^{1.5 + o(1)}\,{\rm log}^{1+o(1)} q+ n^{1 + o(1)}\,{\rm log}^{2+o(1)} q)$ bit operations.