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.