Berlekamp's algorithm (Distinct-degree; Equal-degree Factorization of Polynomials Over Finite Fields)

From Algorithm Wiki
Revision as of 07:56, 10 April 2023 by Admin (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
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

Reference

https://ieeexplore-ieee-org.ezproxy.canberra.edu.au/document/6768643/