Victor Shoup's algorithm (Equal-degree Factorization of Polynomials Over Finite Fields)

Time Complexity

$O(n^{2})$

Space Complexity

$O(n)$ words

(Keeps track of a set of factors, where sum of degrees of factors is $O(n)$ so the total number of terms to keep track of is $O(n)$. Also, polynomials in the separating set can be computed in $O(n)$ space)

Approximate?

Exact

Randomized?

No, deterministic

Model of Computation

Word RAM

Year

1990

Reference

https://www.sciencedirect.com/science/article/abs/pii/0020019090901954