Distinct-degree factorization (Distinct-degree Factorization of Polynomials Over Finite Fields)

Time Complexity

$O(n^{3} + n \log n)$

Space Complexity

$O(n)$ words

(Computes and stores a constant number of polynomials of degree $O(n)$ per iteration. Note that computing $gcd(f, x^{(q^i)}-x)$ can be cleverly done in $O(n)$ space.)

Approximate?

Exact

Randomized?

No, deterministic

Model of Computation

Word RAM

Year

1944

Reference

-