Factoring Polynomials over Finite Fields

A polynomial of degree n over a finite field F q is an expression in an indeterminate x having the form $$f(x) = \sum\limits_{i = 0}^n {{a_i}{x^1}} $$ where n is a non-negative integer, a i ∈ F q , 0 ≤ i ≤ n and a n ≠ 0. To be more precise, f (x) is called a univariate polynomial to distinguish the more general situation where more indeterminates are involved. Most of this chapter will deal with univariate polynomials but the multivariate case will be briefly mentioned at the end.