# 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?

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.