Berlekamp's algorithm (Distinct-degree; 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
(Computes the remainder of $g^{((p-1)/2)}-1 mod f$ (in order to find gcd of $g^{((p-1)/2)}-1$ and f))
Description
Approximate?
Exact
Randomized?
Yes, Monte Carlo
Model of Computation
Word RAM
Year
1967