Cantor–Zassenhaus algorithm (Equal-degree Factorization of Polynomials Over Finite Fields)
Jump to navigation
Jump to search
Time Complexity
$O(n^{3} \log n)$
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, computing h^{((q^d-1)/2)}-1 mod f only requires O(n) space)
Description
Approximate?
Exact
Randomized?
Yes, Monte Carlo
Model of Computation
Word RAM
Year
1981
Reference
https://www.ams.org/journals/mcom/1981-36-154/S0025-5718-1981-0606517-5/home.html