Factorization of polynomials over finite fields: Difference between revisions

Revision as of 03:23, 10 September 2023

Revision as of 09:31, 12 September 2023

Line 49:

{{main article|Berlekamp's algorithm}}

The Berlekamp's algorithm is historically important as being the first factorization algorithm, which works well in practice. However, it contains a loop on the elements of the ground field, which implies that it is practicable only over small finite fields. For a fixed ground field, its [[time complexity]] is polynomial, but, for general ground fields, the complexity is exponential in the size of the ground field.

=== Square-free factorization ===