Let f(x) be a monic polynomial of degree n without repeated factors. We recall from Definition 6.8 that f-reducing polynomials are those polynomials which allow the factorization of f(x). In this chapter, we look into the interesting problem of factorization of polynomials over large finite fields using f-reducing polynomials.
Let f1(x), f2(x), ..., fk(x) be monic irreducible factors in the canonical factorization (see Section 6.3) of f(x) in GF(q) [x], where deg(fi(x)) = ni, 1 ≤ i ≤ k. Let N be the least positive integer such that xqN ≡ x mod f(x). By Theorem 6.10 it follows that
are f-reducing polynomials. It is immediate to check that
Whenever the order of f(x) is known in advance, ...