Factorization of polynomials over finite fields: Difference between revisions

Revision as of 04:54, 15 November 2018

Revision as of 02:02, 28 April 2019

Line 16:

Let ''F'' be a finite field. As for general fields, a non-constant polynomial ''f'' in ''F''[''x''] is said to be [[irreducible polynomial|irreducible]] over ''F'' if it is not the product of two polynomials of positive degree. A polynomial of positive degree that is not irreducible over ''F'' is called ''reducible over'' ''F''.

Irreducible polynomials allow us to construct the finite fields of non-prime order. In fact, for a prime power ''q'', let '''F'''_''q'' be the finite field with ''q'' elements, unique up to an isomorphism. A polynomial ''f'' of degree ''n'' greater than one, which is irreducible over '''F'''_''q'', defines a field extension of degree ''n'' which is isomorphic to the field with ''q''^''n'' elements: the elements of this extension are the polynomials of degree lower than ''n''; addition, subtraction and multiplication by an element of '''F'''_''q'' are those of the polynomials; the product of two elements is the remainder of the division by ''f'' of their product as polynomials; the inverse of an element may be computed by the extended GCD algorithm (see [[Polynomial greatest common divisor|Arithmetic of algebraic extensions]]).

It follows that, to compute in a finite field of non prime order, one needs to generate an irreducible polynomial. For this, the common method is to take a polynomial at random and test it for irreducibility. For sake of efficiency of the multiplication in the field, it is usual to search for polynomials of the shape ''x''^''n'' + ''ax'' + ''b''.{{Citation needed|date=February 2014}}