Go to the first, previous, next, last section, table of contents.


Univariate polynomials on finite fields

In `fff' square-free factorization, DDF (distinct degree factorization), irreducible factorization and primality check are implemented for univariate polynomials over finite fields.

Factorizers return lists of [factor,multiplicity]. The factor part is monic and the information on the leading coefficient of the input polynomial is abandoned. The algorithm used in square-free factorization is the most primitive one.

The irreducible factorization proceeds as follows.

  1. DDF
  2. Nullspace computation by Berlekamp algorithm
  3. Root finding of minimal polynomials of bases of the nullspace
  4. Separation of irreducible factors by the roots


Go to the first, previous, next, last section, table of contents.