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.
The multivariate case admits a polynomial time reduction to the univariate case. For a good discussion of this and related topics (such as factoring sparse polynomials), see Kaltofen's survey, Polynomial factorization 1987–1991, in Proc. Latin '92, Springer LNCS 583 (1992), 294–313.
I believe that it is still open whether there is a deterministic polynomial time factoring algorithm, although some partial results are known assuming the extended Riemann hypothesis.
