The most Efficient Algorithm for Factoring Polynomial Over Finite Field

Question

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)$

Answer 1

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.

Answer 2

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.