best deterministic complexity for factoring polynomials over finite field 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. 
 A: 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.
A: 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." 
A: Check the recent paper by Bourgain, Konyagin and Shparlinski:
CHARACTER SUMS AND DETERMINISTIC POLYNOMIAL ROOT FINDING IN FINITE FIELDS
