Finite Fields, Minimal Polynomials, and Linear Codes

Finite Fields

Sage can easily do computations that are cumbersome by hand. As an example we will find the monic irreducible polynomials of length four over \mathbb{F}_2. By exercise 3.18, each monic irreducible of \mathbb{F}_2[x] of degree four is the minimum polynomial of some element of \mathbb{F}_{2^4}.

We choose 1+x+x^4, a monic irreducible polynomial in \mathbb{F}_2[x] and construct \mathbb{F}_{16}=\mathbb{F}_2[x]/(1+x+x^4) as follows:

We can also do arithmetic with the elements and find the inverse of an element.

If we had chosen a modulus that was not irreducible, we would have gotten the following error message:

To find out if a polynomial is irreducible, and in fact primitive, we can use the following syntax:

Minimal Polynomials

We will now learn to construct minimal polynomials using Sage. We first need to introduce cyclotomic cosets.

Let n be co-prime to q. The q-cyclotomic coset modulo n containing i is defined by

C_i=\{(i \cdot q^j \pmod{n}) \in \mathbb{Z}_n : j=0,1,...\}.

A subset \{i_1,...,i_t\} of \mathbb{Z}_n is called a complete set of representatives of cyclotomic cosets of q modulo n if C_{i_1},...,C_{i_t} are distinct and \cup_{j=1}^tC_{i_j}=\mathbb{Z}_n.

 It is important to note that two cyclotomic cosets are either equal or disjoint, and so the cyclotomic cosets partition \mathbb{Z}_n. 
For example, the cyclotomic cosets of 2 modulo 15 are:

 C_0=\{0\}

 C_1=\{1,2,4,8\}

 C_3=\{3,6,9,12\}

 C_5=\{5,10\}

 C_7=\{7,11,13,14\}

 Thus  C_1=C_2=C_4=C_8 and so on. The set \{0,1,3,5,7\} is a complete set of representatives of 2-cyclotomiccosets modulo 15.

Minimal Polynomials
\beta \in \mathbb{F}_{p^m} \rightarrow \beta^{p^m-1}=1, \rightarrow \beta  is a root of f=1-x^{p^m-1} \in \mathbb{F}_{p}[x].

 Minimal polynomial over \mathbb{F}_{p} of \beta  = polynomial in \mathbb{F}_p of minimal degree with root \beta .

 Example.\mathbb{F}_8 under primitive polynomial f = 1+x^2+x^3.

\alpha a root of f, then \mathbb{F}_8 = \{0,1,\alpha, ..., \alpha^6 \}.

 1\quad m_0(x)\quad = \quad 1+x 

\alpha\quad m_{1}(x) \quad = \quad 1+x^2+x^3 

\alpha^2\quad m_{2}(x) \quad = \quad 1+x^2+x^3 

\alpha^3 \quad m_{3}(x) \quad = \quad 1+x+x^3 

\alpha^4 \quad m_{4}(x) \quad = \quad 1+x^2+x^3 

\alpha^5 \quad m_{5}(x) \quad = \quad 1+x+x^3 

\alpha^6\quad m_{6}(x) \quad = \quad 1+x+x^3 

Some properties

m_{\beta} exists for each \beta \in \mathbb{F}_{p^m}.

m_{\beta} is irreducible over \mathbb{F}_{p}.

m_{\beta} is unique for each \beta.

m_{\beta} is a factor of any polynomial over \mathbb{F}_p for which \beta is a root.

m_{\beta} is an irreducible factor of 1-x^{p^m-1}.

Finding minimal polynomials

 Conjugates of \beta\quad = \quad  roots of \quad m_{\beta}

Example.\mathbb{F}_4=\{0,1,\alpha,\alpha^2\}, \,  with \alpha^2=1+\alpha.

m_{\alpha} = 1+x+x^2,  second root is \alpha^2.

\alpha and 1+\alpha are conjugates.

 Example.\mathbb{F}_8=\{0,1,\alpha,... , \alpha^6\}, where \alpha^3=1+\alpha,

m_{\alpha}=1+x+x^3, \quad  Other roots are \alpha^2, \alpha^4.

 Thus \alpha, \alpha^2  and \alpha^4 are conjugates, and 

m_{\alpha}\quad =\quad 1+x+x^3 \quad = \quad (\alpha + x)(\alpha^2 + x)(\alpha^4 + x ),

Theorem: The conjugates of \beta over \mathbb{F}_p are \beta, \beta^p, ... , \beta^{p^{r-1}}, where r minimum such that \beta^{p^r}=\beta.

Computing minimal polynomials:

 List the conjugates of \beta and compute the product

 m_{\beta} \quad = \quad (\beta - x)(\beta^p - x) \cdots (\beta^{p^{r-1}} - x ) 

Since \beta \in \mathbb{F}_{p^m}, \beta=\alpha^j for j\in\{1,...,m-2\}, where \alpha is a root of the primitive polynomial used to construct \mathbb{F}_{p^m}. Then

 Consider \mathbb{F}_{2^4} that we constructed earlier and recall that a is a root of  1+x+x^4, the monic irreducible polynomial we used to construct the field. In fact, 1+x+x^4 is primitive, so every nonzero element can be expressed as a power of a.  Now it is easy to find the monic irreducible polynomials of degree 4 over \mathbb{F}_2. The 2-cyclotomic cosets modulo 2^4-1= 15 are C_0=\{0\}, C_1=\{1,2,4,8\}, C_3=\{3,6,9,12\}, C_5=\{5,10\}, C_7=\{7,11,13,14\}.

Thus the minimum polynomial of a^3 is (x-a^3)(x-a^6)(x-a^9)(x-a^{12})  and the minimum polynomial of a^7 is (x-a^7)(x-a^{11})(x-a^{13})(x-a^{14}) and of course we already know the minimum polynomial of a is 1+x+x^4.

Actually, there is a command for that.

Problem 1. Find a monic irreducible polynomial f(x), of degree 7 over \mathbb{F}_3, and let a be a root of f(x). Find the minimal polynomials of a^2 and a^3.

Answer: To find a monic irreducible polynomial of degree 7 over \mathbb{F}_3 we guess and check.

 The cyclotomic coset of 3 modulo 3^7-1 containing 1 is C_1= \{1,3,9,27,81,243,729\}, So C_2=\{2,6,18,54,162,486,1458\} Since 3 is in the same coset as 1, the minimal polynomial of a and a^3 are the same and we already know the minimal polynomial of a since we used it to construct \mathbb{F}_{3^7}. Thus M_{a}=M_{a^3}=x^7+x^6+x^5+x^4+1. Then to find the minimal polynomial of a^2, we multiply 

(x-a^2)(x-a^6)(x-a^{18})(x-a^{54})(x-a^{162})(x-a^{486})(x-a^{1458}) and get:

Problem 2. Factor x^{24}-1 over \mathbb{F}_7.

Problem 3. Factor x^{40}-1 over \mathbb{F}_3.

Constructing Linear Codes

To construct liner codes, one must first construct the proper Matrix Space. The example that follows gives a name , MS, for the set of matrices with entries in \mathbb{F}_3 that have 4 rows and 9 columns.

Now we list our generating set of codewords.

Finally, We construct our linear code C.

Here are some useful commands that you may need:

This command gives us the generator matrix of the code.

To get a generator matrix is systematic form, we can use:

We can also get the parity check matrix.

If we want to multiply a vector by a matrix, we first have to declare the proper vector space, and then use the following syntax to create a vector:

If v is a message that we wish to encode by multiplying it by G, we do so as follows:

Here we are creating a vector of length 9. We then see if this vector, r, is a codeword.

Here are some more helpful functions.

Problem 4. Let a be a primitive element of \mathbb{F}_4, and let C be the \mathbb{F}_4-linear code with generator matrix \begin{matrix} 1&0&0&1&a&a\\0&1&0&a&1&a\\0&0&1&a&a&1\end{matrix}. Is C self dual? Is C equivalent to C^{\perp}?

Problem 5. Construct a linear code C over \mathbb{F}_{32} such that the generator matix is (I_n|A) where I_n is an n\times n identity matrix and A is symmetric (equal to its transpose). Show that C is equivalent to C^{\perp}.

Problem 6. Construct a linear code C over \mathbb{F}_{8} of length 11 and dimension 5. Find its minimal distance.  Form a message vector of length 5 over the same field and encode it by multiplying it by the generator matrix of C. Change the encoded word by adding an error vector to it of weight less than or equal to d-1. Confirm that this word is not a codeword by multiplying it by the check matrix for the code.