Math 361, Spring 2020, Assignment 15

"Reeling and Writhing, of course, to begin with," the Mock Turtle replied; "And then the different branches of Arithmetic - Ambition, Distraction, Uglification, and Derision."

- Lewis Carroll, Alice's Adventures in Wonderland

Read:

1. Section 33.

Carefully define the following terms:

1. $GF(q)$ (a.k.a. $\mathbb{F}_q$, where $q=p^n$ is a prime power).

Carefully state the following theorems (you do not need to prove them):

1. Theorem constraining the order of a finite field.
2. Theorem relating finite fields of the same order.
3. Theorem concerning the existence of finite fields with a given order.
4. Theorem concerning the roots of $x^q-x$ in a field $F$ of order $q$.

Solve the following problems:

1. Section 33, problems 1, 2, 3, and 4.
2. (Arithmetic in $\mathbb{F}_{16}$)

(a) Show that the polynomial $x^4+x+1$ is irreducible over $\mathbb{Z}_2$.

(b) Thus, the ring $$\mathbb{F}_{16}=\mathbb{Z}_2[x]/\left\langle x^4+x+1\right\rangle=\{c_3\alpha^3+c_2\alpha^2+c_1\alpha+c_0\,|\,c_i\in\mathbb{Z}_2\}$$ is a field with $16$ elements. In compact notation, we write $c_3,c_2,c_1,c_0$ to indicate the element $c_3\alpha^3+c_2\alpha^2+c_1\alpha+c_0$ (and, since the coefficients can always be represented with a single digit, we usually omit the commas). For example, the element $\alpha^3+\alpha$ is written $1010$. It is always easy to add elements of $\mathbb{F}_{16}$ in compact notation, since we just add columnwise modulo two. For example, $1101 + 1011 = 0110$. Choose several random pairs of elements of $\mathbb{F}_{16}$, and add them. Then subtract them also.

(c) Working in compact notation, make a table of the powers of $\alpha$. To get you started, here are the first few entries: $$\begin{array}{c|c}i&\alpha^i\\\hline 0&0001 \\ 1&0010 \\ 2&0100 \\ 3&1000 \\ 4&0011 \\ 5&0110 \\ \vdots&\vdots \end{array}$$ As a check, recall that we must have $\alpha^{15}=0001$.

(d) You should have found above that the powers of $\alpha$ sweep out all of the non-zero elements of $\mathbb{F}_{16}$. For this reason, $\alpha$ is said to be a primitive element of $\mathbb{F}_{16}$ (and $x^4+x+1$ is said to be a primitive polynomial in $\mathbb{Z}_2[x]$, since it is the minimal polynomial of a primitive element in the field it produces). A table of powers of a primitive element is called an index table for the field; thus, in the previous part, you have produced an index table for $\mathbb{F}_{16}$. Index tables make it easy to multiply in a finite field; one uses the table to convert elements to powers of the primitive element, then one multiplies by adding exponents and converting the result back to compact notation. For example, $$(0100)\cdot(1000)=\alpha^2\cdot\alpha^3=\alpha^5=(0110).$$ Here is another example, which you should be able to reproduce using your index table: $$(1011)\cdot(0111)=\alpha^7\cdot\alpha^{10}=\alpha^{17}=\alpha^2=(0100).$$ (We have $\alpha^{17}=\alpha^2$ because $\alpha^{15}=1$.) Choose several random pairs of elements of $\mathbb{F}_{16}$, and multiply them using your index table.

(e) An index table also makes it easy to invert elements, since the identity $\alpha^{15}=1$ implies that the inverse of $\alpha^i$ is $\alpha^{15-i}$. For example, $$(0110)^{-1}=(\alpha^5)^{-1}=\alpha^{15-5}=\alpha^{10}=(0111).$$ Choose several random elements of $\mathbb{F}_{16}$ and invert them.

(f) Choose several random pairs of elements and divide them. Now you know how to add, subtract, multiply, and divide.

3. (Linear algebra over $\mathbb{F}_{16}$)

(a) Consider the following system of linear equations, in which the variables stand for elements of $\mathbb{F}_{16}$: $$\begin{align*}(0110)\cdot x + (1010)\cdot y &= (1110) \\ (0010)\cdot x + (1111)\cdot y &= (1011).\end{align*}$$ Write the augmented matrix of this system, then use the Gauss-Jordan algorithm to compute the reduced row-echelon form of this matrix, thus solving the system.

(b) Working in the vector space $\mathbb{F}_{16}^2$, determine whether the vectors $$\vec{v}_1=\begin{bmatrix}0101\\0011\end{bmatrix}, \vec{v}_2=\begin{bmatrix}1101\\1010\end{bmatrix}$$ are linearly independent. If they are linearly dependent, then find a non-trivial linear relation between them. (Hint: form the matrix $\begin{bmatrix}\vec{v}_1&\vec{v}_2\end{bmatrix}$ and row-reduce to compute the kernel, which as you recall can be interpreted as the set of linear relations among the columns. It is true that in this example, a clever use of the index table will allow you to answer the question without row-reduction, but this technique would not generalize well to larger problems.)

--------------------End of assignment--------------------