The most Efficient Algorithm for Factoring Polynomial Over Finite Field I have a polynomial defined over a finite field $\mathbb{F}_p$, where $p$ is a large prime number (e.g. 256-bit).
The polynomail's degree is big (e.g. at least $10^5$). 
My Goal is: To find the roots of the polynomial. 
One way to do that is to factorize the polynomial then find the low degree polynomials'roots. My polynomial can be constructed to be a monic polynomial (if this helps to speed up the proceess). Here, how fast I can find the roots matters to me.
Question: What is the most efficient algorithm that factorize the polynomial over a finite field.
I am aware of this paper: http://www.shoup.net/papers/lille.pdf
but I want something faster e.g. $O(n)$
 A: Concerning the complexity of factorizations, I believe the best current result is
Kedlaya, Umans:
Fast polynomial factorization and modular composition.
SIAM J. Comput. 40 (2011), no. 6, 1767–1802. 
which gives complexity of roughly $(n^{1.5}+n\log q)\log q$ for a field with $q$ elements.
A: There is a nice probabilistic algorithm to find the roots of a polynomial mod $p$ that might suit you, though I'm not sure of it's complexity. It is described in Cohen's A course in computational number theory pages 36-38. If $G(X)$ is your polynomial then first compute
    $$ F(X) = \operatorname{gcd}(X^p-X,G(X)) $$
Now $F(X)$ has only linear factors and now 
the key idea es to use a series of random $a\pmod p$ and find the gcd of $F(X)$ and  $(X-a)^{\frac{p-1}2}-1$, modulo $p$. Suppose you get
   $$ A(X) = \operatorname{gcd} ((X-a)^{\frac{p-1}2}-1,F(X)) $$
Then $A(X)$ is a factor of $F(X)$ if it is not trivial, you can repeat the algorithm with $F(X)/A(X)$ and $A(X)$ until you get linear or quadratic factors that you can solve directly.
As $(X-a)^{\frac{p-1}2}-1$ is a very large polynomial you have first to compute 
 $$ (X-a)^{\frac{p-1}2} \pmod{p,F(X)} $$
using the power algorithm and working modulo $p$ and modulo $F(X)$. And the same for $X^p-X$.
It works because the factors of $(X-a)^{\frac{p-1}2}-1 \pmod p$ are all the integers $u$ such that $u-a$ is a quadratic residue, and this splits "randomly" the integers mod $p$ in two halves, and the gcd picks the factors in each set. 
