Skip to main content

Algebraic Coding Theory MATH 4012 Spring 2026

Dr. Hunter Lehmann

Print preview

Paper size
Additional printing options
Print headers
Print footers

Worksheet Order, Characteristic, and Zech’s Logs

Today we will continue our investigation of computation in finite fields, considering the order of elements, the characteristic of the field, the existence of primitive elements, and Zech’s logarithms. We will explore how these concepts are interconnected and how they can be used to perform computations in finite fields efficiently.
🔗

Definition 60. Characteristic of a Field.

The characteristic of a field is the smallest positive integer \(\char(F) = p\) such that
\begin{equation*} p \cdot 1 = \underbrace{1 + 1 + \cdots + 1}_{p \text{ times}} = 0 \end{equation*}
in the field. If no such \(p\) exists, the characteristic is defined to be zero.
🔗
🔗

1. Characteristic of \(\Q\).

What is the characteristic of the field of rational numbers \(\Q\text{?}\)
🔗
Solution.
The characteristic of the field of rational numbers \(\Q\) is zero, because there is no positive integer \(p\) such that
\begin{equation*} p \cdot 1 = 0 \end{equation*}
in \(\Q\text{.}\)
🔗
🔗
🔗

2. Characteristic is Prime.

Show that the characteristic of a finite field is always a prime number by considering a factorization of the integer \(p\) and using field properties to show that one of the factors must be \(p\text{.}\)
🔗
Solution.
Let \(p\) be the characteristic of a finite field \(F\text{.}\) Since \(F\) is finite, we must have positive characteristic. By definition, we have
\begin{equation*} p \cdot 1 = 0 \end{equation*}
in \(F\text{.}\) Suppose we have \(p = ab\text{.}\) Then
\begin{equation*} (a \cdot 1)(b \cdot 1) = (ab) \cdot 1 = p \cdot 1 = 0 \end{equation*}
Since \(F\) is a field, it has no zero divisors, which means that either
\begin{equation*} a \cdot 1 = 0 \end{equation*}
or
\begin{equation*} b \cdot 1 = 0\text{.} \end{equation*}
Since \(p\) is the smallest positive integer such that
\begin{equation*} p \cdot 1 = 0\text{,} \end{equation*}
it follows that either \(a = p\) or \(b = p\text{.}\) Therefore, the characteristic \(p\) must be prime.
🔗
🔗
🔗

Definition 61. Prime Subfield.

The prime subfield of a field \(F\) is the smallest subfield of \(F\text{.}\) When the characteristic of \(F\) is zero, the prime subfield is isomorphic to the field of rational numbers \(\Q\text{.}\) When the characteristic of \(F\) is a prime number \(p\text{,}\) the prime subfield is isomorphic to the finite field \(\F_p\text{.}\)
🔗
🔗

3. Finite Fields Have Prime Power Size.

Use the idea of the prime subfield together with extension degree to explain why every finite field has size a power of a prime number.
🔗
Solution.
Let \(F\) be a finite field. Then it has prime characteristic \(p\) and a prime subfield isomorphic to \(\F_p\text{.}\) By our previous results, since \(F\) is an extension field of \(\F_p\) and is finite it has some finite extension degree \(n\text{.}\) Then the number of elements in \(F\) is \(|F| = p^n\)
🔗
🔗
🔗

4.

Consider \(F=\F_3[x]/(x^2+1)\text{.}\) Determine if \(\alpha=x\) is a primitive element.
🔗
Solution.
The element \(\alpha\) is not primitive. We have \(\alpha^2=-1=2\) in \(F\text{,}\) so \(\alpha^4=2^2=1\text{,}\) so the powers of \(\alpha\) are \(\alpha^0=1\text{,}\) \(\alpha^1=\alpha\text{,}\) \(\alpha^2=2\text{,}\) and \(\alpha^3=2\alpha\text{.}\) Since there are only 4 distinct powers of \(\alpha\text{,}\) it cannot be a primitive element, which would require 8 distinct powers.
🔗
🔗
🔗

Definition 62. Zech’s Log Table.

Fix a primitive element \(\alpha\) in a finite field \(F\) of order \(q\text{.}\) For each integer \(i, 1\leq i \leq q-2\text{,}\) define the Zech’s log value \(z(i)\) to be the unique integer \(j=z(i)\) such that
\begin{equation*} 1+\alpha^i = \alpha^j\text{.} \end{equation*}
🔗
The Zech’s log table for the field \(F\) with respect to the primitive element \(\alpha\) is the list of pairs \((i, z(i))\) for each integer \(i, 0\leq i \leq q-2\text{,}\) together with the pair \((-\infty,0)\) to handle the element \(0\text{.}\) We will also have \(z(i)=-\infty\) when \(i\) is the integer for which \(\alpha^i=-1\text{.}\) If \(\char(F)=2\text{,}\) this is \(0\text{,}\) and if \(\char(F)\gt 2\) (and hence odd) it is \((q-1)/2\text{.}\)
🔗
🔗

5.

Construct the Zech’s log table for the field \(F=\F_3[x]/(x^2+1)\) with primitive element \(\alpha=x+1\text{.}\)
🔗
Solution.
To construct the table, we know already from the above that \(z(-\infty)=0\) and \(z((9-1)/2))=z(4)=-\infty\text{.}\) For the other elements, we compute the power of \(\alpha=x+1\) such that \(1+(x+1)^i=(x+1)^{z(i)}\text{.}\) The easiest approach to this is to first build the table of powers of \(\alpha\) as in the Daily Prep and extract the results from there. So we show this approach.
🔗
\(i\) \((x+1)^i\)
\(0\) \(1\)
\(1\) \(x+1\)
\(2\) \(2x\)
\(3\) \(2x+1\)
\(4\) \(2\)
\(5\) \(2x+2\)
\(6\) \(x\)
\(7\) \(x+2\)
Now we can use this to assign the Zech’s log values. From this we see that \(1+(1+x)^0=1+1=2=(1+x)^4\text{,}\) so \(z(0)=4\text{.}\) Similarly \(1+(1+x)^1=1+1+x=2+x=(1+x)^7\text{,}\) so \(z(1)=7\text{,}\) and so on.
🔗
\(i\) \(z(i)\)
\(-\infty\) \(0\)
\(0\) \(4\)
\(1\) \(7\)
\(2\) \(3\)
\(3\) \(5\)
\(4\) \(-\infty\)
\(5\) \(2\)
\(6\) \(1\)
\(7\) \(6\)
🔗
🔗

6.

To compute \(\alpha^a+\alpha^b\) with this table, we can rewrite the sum as \(\alpha^a(1+\alpha^{b-a})=\alpha^a \alpha^{z(b-a)}\text{.}\) Compute \(\alpha^5+\alpha^3\) using this method and the Zech’s log table you constructed in the previous exercise.
🔗
Solution.
We have
\begin{align*} \alpha^5+\alpha^3 \amp = \alpha^3(1+\alpha^2)\\ \amp = \alpha^3 \alpha^{z(2)}\\ \amp = \alpha^3 \alpha^3\\ \amp \alpha^6\text{.} \end{align*}
In other words, in this field we have \((1+x)^5+(1+x)^3=(1+x)^6=x\) (using the other lookup table to do the last conversion, although the point of this method is to only ever have to use the power of a primitive element representation of our field elements.
🔗
🔗
🔗

7.

What are some advantages of using Zech’s log tables for computations in finite fields versus other representations we’ve seen? What are some limitations of using Zech’s log tables?
🔗
Solution.
The major advantage is that we can do both addition and multiplication quickly with very few operations and only one table look up for the logarithm. The major limitation is that we have to have the table precomputed, which is not practical for large fields.
🔗
🔗
🔗
🔗
PrevTopNext