Paper
Part IIIFinite Fields and Their Arithmetic

Rings and Fields

November 16, 202654 min readbeginner

Bytes add and multiply in two ways inside a processor, and neither allows division. This chapter names the rules they share, the ring, finds the zero divisors that block division, and proves a finite field has p^m elements.

Most codes of Linear Block Codes, the part that ends just before this chapter, were binary, so their arithmetic was XOR and AND on single bits. The codes ahead work on larger symbols. A Reed–Solomon code treats a multi-bit symbol, such as a byte, as one symbol [1], and a BCH code is built from a field whose elements are several bits wide [2]. Both need an arithmetic on multi-bit words in which every nonzero word can be divided by.

A processor already holds two arithmetics on bytes, the integers modulo 256 that a multiply instruction computes when it keeps the low byte, and the bitwise XOR and AND of the logic unit. In neither can every nonzero byte be divided by, and the reason is the same in both, a product of two nonzero bytes that comes out zero. This chapter names the rules such systems share, the ring, and finds exactly which rings allow division. Those are the fields, and this part, Finite Fields and Their Arithmetic, builds the finite ones.

The chapter checks the ring axioms on eight small rings and splits the nonzero elements of a finite ring into units and zero divisors. Integral domains and fields follow, and the last sections show why characteristic 2 frees an adder from its carry chain, prove that (a+b)p=ap+bp(a + b)^p = a^p + b^p in characteristic pp, and show that every finite field has a prime power of elements.

Every number in the chapter is recomputed by ch32_rings_and_fields.py in the python/ folder of the companion repository ecc-book-lab, and the charts are drawn by ch32_charts.py in the same folder. The GNU Octave twin ch32_rings_and_fields.m prints the same lines, as The Octave Route explains.

01.Two Rings Inside an 8-Bit Processor

A processor that multiplies two bytes and keeps only the low 8 bits of the product computes the product modulo 256, because every dropped bit is worth a multiple of 256. Take the multiplier 3. The product 3⋅171=513=2⋅256+13 \cdot 171 = 513 = 2 \cdot 256 + 1 keeps the low byte 1, so 3⋅171≡1(mod256)3 \cdot 171 \equiv 1 \pmod{256}, and multiplying by 171 undoes multiplying by 3. The companion script checks this on all 256 bytes, and as xx runs over them, 3x3x takes all 256 values.

The multiplier 2 behaves differently. Since 2⋅0=02 \cdot 0 = 0 and 2⋅128=256≡02 \cdot 128 = 256 \equiv 0, two different bytes map to 0, and 2x2x takes only 128 values, the even ones. Once two inputs share an output, no later multiplication can separate them, so no byte undoes multiplication by 2. The cause is 2⋅128≡02 \cdot 128 \equiv 0, two nonzero factors with a zero product.

The logic unit holds a second arithmetic on the same bytes, with XOR as the addition and AND as the multiplication. The bytes 0x0F and 0xF0 are both nonzero, yet 0x0F AND 0xF0 is 0, while their XOR is 0xFF, which is 255. Again two nonzero factors multiply to zero, and again division fails, for every byte except 0xFF.

These two arithmetics obey one list of rules, as do the integers, the polynomials and the square matrices. That list defines a ring, and it lets each theorem below be proved once and then applied to all of them.

02.The Ring Axioms

In the integers modulo 12, 5⋅(7+9)=5⋅4=20≡85 \cdot (7 + 9) = 5 \cdot 4 = 20 \equiv 8, and 5⋅7+5⋅9=80≡85 \cdot 7 + 5 \cdot 9 = 80 \equiv 8, so multiplication distributes over addition just as it does for ordinary integers. A ring keeps that law and a few others and asks for nothing more.

a(b+c)=ab+ac,(a+b)c=ac+bca(b + c) = ab + ac, \qquad (a + b)c = ac + bc
(1)

The words for addition come from Groups and Cosets. Addition must form an abelian group, so subtraction a−b=a+(−b)a - b = a + (-b) always works. Multiplication is asked for much less. It need not commute, and an element need not have an inverse, which is exactly the freedom that lets 2 fail modulo 256. The distributive laws alone tie the two operations together, and nearly every proof below runs through them. Some books leave the element 1 out of the definition, and every ring in this book has one. Book-length treatments of rings and finite fields, one written for mathematicians and one for engineers, are [3] and [4].

The companion script checks every axiom by brute force on eight finite rings, over every pair and every triple of elements, which comes to 16,777,216 triples for the integers modulo 256 and as many for the 8-bit words under XOR and AND. The other six are the integers modulo 4, 12 and 13, the 2-bit words, the 2 by 2 matrices over GF(2)\mathrm{GF}(2), and a four-element field met later. Every axiom holds in all eight, and all but the matrices are commutative. In the rings of words the one is the all-ones word, because a bit ANDed with 1 is unchanged.

Seven rings recur through the book, and Table 1 lists their sizes, zeros and ones. The integers are the model for all of them, and the integers modulo nn from Integers and Modular Arithmetic are the first finite examples.

Table 1. Seven rings with their size, zero, one and whether multiplication commutes

RingElementsZeroOneCommutative
Z\mathbb{Z}infinitely many0011yes
Z12\mathbb{Z}_{12}120011yes
Z256\mathbb{Z}_{256}2560011yes
Z[x]\mathbb{Z}[x]infinitely many0011yes
GF(2)[x]\mathrm{GF}(2)[x]infinitely many0011yes
8-bit words, XOR and AND2560000000011111111yes
M2(GF(2))M_2(\mathrm{GF}(2))16zero matrixidentity matrixno

For a commutative ring RR, the polynomial ring R[x]R[x] holds the polynomials with coefficients in RR, added coefficient by coefficient and multiplied by distributing every term over every term. The coefficients matter. Over the integers (x2+x+1)(x+1)=x3+2x2+2x+1(x^2 + x + 1)(x + 1) = x^3 + 2x^2 + 2x + 1, while over GF(2)\mathrm{GF}(2) each 2 vanishes and the product is x3+1x^3 + 1, the bit string 1001. Each ring axiom for R[x]R[x] reduces to one in RR, because the coefficient of xkx^k in fgfg is ∑i+j=kfigj\sum_{i + j = k} f_i g_j, so (fg)h(fg)h and f(gh)f(gh) share the coefficient ∑i+j+l=kfigjhl\sum_{i + j + l = k} f_i g_j h_l, and the other laws follow alike. Polynomials over a Field develops division and roots.

The nn-bit words form a ring under XOR and AND, each bit position a separate copy of GF(2)\mathrm{GF}(2). Two facts make this ring odd, a∧a=aa \wedge a = a and a⊕a=0a \oplus a = 0 for every byte aa, with ∧\wedge for AND and ⊕\oplus for XOR.

The 2 by 2 matrices over GF(2)\mathrm{GF}(2), written M2(GF(2))M_2(\mathrm{GF}(2)), form a ring of 16 elements under the entrywise sum and the matrix product of Matrices and Elimination over Finite Fields. It is not commutative.

A=(1101),B=(1011),AB=(0111),BA=(1110)A = \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}, \quad B = \begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix}, \quad AB = \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}, \quad BA = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}

The two products differ, so every statement about this ring has to say on which side a factor stands.

04.First Consequences of the Axioms

In every ring of the gallery, 0⋅a=00 \cdot a = 0 and (−a)b=−(ab)(-a)b = -(ab). Neither fact is an axiom. Both follow from the distributive laws, and the companion script confirms them in all eight finite rings, along with the uniqueness of the zero, the one and each negative.

Proof. Since 0=0+00 = 0 + 0, the distributive law gives 0a=(0+0)a=0a+0a0a = (0 + 0)a = 0a + 0a. Adding −(0a)-(0a) to both sides leaves 0=0a0 = 0a, and the other distributive law gives a0=0a0 = 0 the same way. Next, ab+(−a)b=(a+(−a))b=0b=0ab + (-a)b = (a + (-a))b = 0b = 0, so (−a)b(-a)b is a negative of abab. The group (R,+)(R, +) has only one negative for each element, by Lemma: One identity and one inverse in Groups and Cosets, so (−a)b=−(ab)(-a)b = -(ab). The same steps applied to a(b+(−b))=0a(b + (-b)) = 0 give a(−b)=−(ab)a(-b) = -(ab). Finally (−a)(−b)=−(a(−b))=−(−(ab))=ab(-a)(-b) = -(a(-b)) = -(-(ab)) = ab, since the negative of a negative is the element itself. ■\blacksquare

Proof. The zero is the identity of the group (R,+)(R, +), which is unique by the same lemma of Groups and Cosets. If 11 and 1′1' both act as identities, then 1=1⋅1′=1′1 = 1 \cdot 1' = 1', where the first equality uses 1′1' as an identity and the second uses 11. If 1=01 = 0, every element satisfies a=1a=0a=0a = 1a = 0a = 0 by the previous lemma. ■\blacksquare

The one-element ring is called the zero ring. It satisfies every axiom and is useless for arithmetic, so the definitions of integral domain and field below exclude it by asking for 1≠01 \ne 0.

05.Ring Homomorphisms

To check 47⋅86=404247 \cdot 86 = 4042 without redoing the multiplication, reduce every number modulo 9. The factors leave 2 and 5, and 2⋅5=102 \cdot 5 = 10 leaves 1. The claimed product leaves 1 as well, as Equation 2 records, so the check passes, while a wrong product such as 4052 leaves 2 and is exposed. The check works because reduction modulo 9 respects both addition and multiplication.

4042 mod 9=1=(2⋅5) mod 9,4052 mod 9=24042 \bmod 9 = 1 = (2 \cdot 5) \bmod 9, \qquad 4052 \bmod 9 = 2
(2)

A ring homomorphism is thus a homomorphism of the additive groups, in the sense of Groups and Cosets, that also respects products and sends the one to the one.

Proof. By the definition of a remainder, r(a)≡a(modn)r(a) \equiv a \pmod{n} for every integer aa. Theorem: Congruence respects addition and multiplication, in Integers and Modular Arithmetic, then gives r(a)+r(b)≡a+br(a) + r(b) \equiv a + b and r(a)r(b)≡abr(a) r(b) \equiv ab. The sum and the product in Zn\mathbb{Z}_n are those integers reduced modulo nn, and two numbers from 0 to n−1n - 1 that are congruent are equal, so the sum of r(a)r(a) and r(b)r(b) in Zn\mathbb{Z}_n is r(a+b)r(a + b) and their product is r(ab)r(ab). Since n≥2n \ge 2, r(1)=1r(1) = 1. Finally r(a)=0r(a) = 0 means exactly that nn divides aa. ■\blacksquare

The theorem is the congruence theorem restated in the language of rings, and the companion script checks both equations for every nn from 2 to 12 and every aa and bb from −30-30 to 30. Ideals and Quotient Rings studies kernels in general, and the kernel of a reduction of polynomials turns out to be the way to new fields.

Arithmetic Codes and Checking Logic used residues in exactly this way, and the theorem is what makes a residue check on a multiplier sound. A correct product never raises an alarm, and a wrong result with error ee escapes exactly when ee lies in the kernel. The error in 4052 is 10, not a multiple of 9, so the check catches it.

06.Units and Zero Divisors

Row 5 of the multiplication table modulo 12 holds a 1 in column 5, and rows 7 and 11 hold a 1 on the diagonal as well. Row 4 holds a 0 in column 3, since 4⋅3=12≡04 \cdot 3 = 12 \equiv 0, and row 6 holds a 0 in column 2. Figure 1 marks both kinds of row.

Multiplication table modulo 12 with its units and zero divisors marked multiplication mod 12 x 0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 3 4 5 6 7 8 9 10 11 0 2 4 6 8 10 0 2 4 6 8 10 0 3 6 9 0 3 6 9 0 3 6 9 0 4 8 0 4 8 0 4 8 0 4 8 0 5 10 3 8 1 6 11 4 9 2 7 0 6 0 6 0 6 0 6 0 6 0 6 0 7 2 9 4 11 6 1 8 3 10 5 0 8 4 0 8 4 0 8 4 0 8 4 0 9 6 3 0 9 6 3 0 9 6 3 0 10 8 6 4 2 0 10 8 6 4 2 0 11 10 9 8 7 6 5 4 3 2 1 unit: its row holds a 1 zero divisor: its row holds a 0 off the zero column product 1: an inverse pair product 0 of two nonzero factors Units 1, 5, 7, 11. Zero divisors 2, 3, 4, 6, 8, 9, 10. The element 0 is neither.
Figure 1. The multiplication table modulo 12. Every unit has a 1 in its row and every zero divisor has a 0 off the zero column, and no nonzero element has both. Data: computed by ch32_charts.py in the companion repository.

Proof. If ab=ba=1ab = ba = 1 and ab′=b′a=1ab' = b'a = 1, associativity gives b=b1=b(ab′)=(ba)b′=1b′=b′b = b 1 = b(ab') = (ba)b' = 1 b' = b'. ■\blacksquare

In Z12\mathbb{Z}_{12} the units are 1, 5, 7 and 11, each its own inverse because each squares to 1. The zero divisors are 2, 3, 4, 6, 8, 9 and 10, and 0 is neither.

(ab)−1=b−1a−1(ab)^{-1} = b^{-1} a^{-1}
(3)

Proof. Take units aa and bb. Associativity gives (ab)(b−1a−1)=a(bb−1)a−1=a⋅1⋅a−1=1(ab)(b^{-1} a^{-1}) = a (b b^{-1}) a^{-1} = a \cdot 1 \cdot a^{-1} = 1 and (b−1a−1)(ab)=b−1(a−1a)b=b−1b=1(b^{-1} a^{-1})(ab) = b^{-1} (a^{-1} a) b = b^{-1} b = 1, so abab is a unit with the inverse claimed. That is closure. Multiplication is associative in RR, hence in R∗R^*. The identity 1 is a unit, since 1⋅1=11 \cdot 1 = 1. For each unit aa, the equations aa−1=a−1a=1a a^{-1} = a^{-1} a = 1 also say that a−1a^{-1} is a unit with inverse aa. Every group axiom holds. ■\blacksquare

Lemma: The units modulo n form a group, in Groups and Cosets, is the case R=ZnR = \mathbb{Z}_n, where closure needed Bezout's identity. Here closure is immediate, because abab comes with the inverse b−1a−1b^{-1} a^{-1}. In Z256\mathbb{Z}_{256} the units are the 128 odd bytes, and the inverse of 3 is 171, as the opening found.

Proof. If ab=0ab = 0, then b=1b=(a−1a)b=a−1(ab)=a−10=0b = 1 b = (a^{-1} a) b = a^{-1} (ab) = a^{-1} 0 = 0, using associativity and the lemma on zero. If ba=0ba = 0, then b=b(aa−1)=(ba)a−1=0b = b (a a^{-1}) = (ba) a^{-1} = 0. ■\blacksquare

The only units of the integers are −1-1 and 11. If ab=1ab = 1 for integers aa and bb, then ∣a∣⋅∣b∣=1|a| \cdot |b| = 1 with both factors whole numbers of size at least 1, so ∣a∣=1|a| = 1 and a=±1a = \pm 1.

In the 8-bit words, a∧b=11111111a \wedge b = 11111111 forces every bit of aa to be 1, so the one, 11111111, is the only unit. Every other nonzero word aa has a 0 bit, so its complement ¬a\neg a is nonzero and a∧¬a=0a \wedge \neg a = 0, which makes all 254 of them zero divisors. The 2-bit words show the same in miniature, with the single unit 11 and the zero divisors 01 and 10.

The matrix ring has 6 units, which is the count (22−1)(22−2)(2^2 - 1)(2^2 - 2) given by Theorem: Counting invertible matrices in Matrices and Elimination over Finite Fields, and the script finds that each of the other 9 nonzero matrices has a nonzero partner on each side that multiplies it to zero.

07.Every Element of a Finite Ring Is One or the Other

Multiplication by 3 modulo 7 sends 0,1,…,60, 1, \ldots, 6 to 0,3,6,2,5,1,40, 3, 6, 2, 5, 1, 4. Every output appears once, and the output 1 comes from the input 5, so 3 is a unit. Multiplication by 2 modulo 6 sends 0,1,…,50, 1, \ldots, 5 to 0,2,4,0,2,40, 2, 4, 0, 2, 4, and the collision of the inputs 0 and 3 gives 2⋅3≡02 \cdot 3 \equiv 0. Figure 2 draws both maps, and the next theorem shows that these are the only two possibilities.

Multiplication by 3 modulo 7 is one to one, multiplication by 2 modulo 6 is not times 3 mod 7 x 3x 0 0 1 1 2 2 3 3 4 4 5 5 6 6 every output hit once, so 3 is a unit times 2 mod 6 x 2x 0 0 1 1 2 2 3 3 4 4 5 5 0, 2, 4 hit twice, 1, 3, 5 never Green arrow: 3 times 5 is 1 mod 7. Dashed red arrows: a second input landing on an output already hit.
Figure 2. Multiplication by 3 modulo 7 is one to one, so it reaches 1 and 3 is a unit. Multiplication by 2 modulo 6 sends two inputs to each even output, so 2 is a zero divisor. Data: computed by ch32_charts.py in the companion repository.

Proof. Fix a nonzero element aa and consider the map ma(x)=axm_a(x) = ax from the ring to itself. Suppose first that mam_a is one to one. Then its outputs are as many as the elements of the ring, so they are all of them, and some bb has ab=1ab = 1. Commutativity gives ba=1ba = 1 too, so aa is a unit. Suppose instead that ax=ayax = ay for some x≠yx \ne y. The distributive law and the lemma on signs give a(x−y)=ax−ay=0a(x - y) = ax - ay = 0 with x−y≠0x - y \ne 0, so aa is a zero divisor. No element is both, by Lemma: A unit is never a zero divisor. ■\blacksquare

Finiteness is essential. In the integers, multiplication by 2 is one to one but misses 1, so 2 is not a unit, and since a product of nonzero integers has size at least 1, it is not a zero divisor either.

Proof. The case d=1d = 1 is Theorem: When an inverse exists, in Integers and Modular Arithmetic. If d≥2d \ge 2, write a=da′a = d a'. Then a⋅(n/d)=a′n≡0a \cdot (n/d) = a' n \equiv 0, and n/dn/d lies strictly between 0 and nn because d≥2d \ge 2, so it is a nonzero element of Zn\mathbb{Z}_n. ■\blacksquare

In Z256\mathbb{Z}_{256} the partner 128 serves every even byte, since 2k⋅128=256k≡02k \cdot 128 = 256 k \equiv 0. In general Zn\mathbb{Z}_n has φ(n)\varphi(n) units and n−1−φ(n)n - 1 - \varphi(n) zero divisors, which the script confirms for every nn from 2 to 40 and Figure 3 plots. Only a prime modulus has no zero divisor at all.

The number of units and of zero divisors in the integers modulo n, for n from 2 to 40 0 10 20 30 40 2 5 10 15 20 25 30 35 40 n, the modulus count n - 1, every nonzero element units, n composite units, n prime zero divisors Units and zero divisors always add up to n - 1. Only a prime modulus has no zero divisor.
Figure 3. The number of units and of zero divisors in the integers modulo n, for n from 2 to 40. The two counts always add up to n minus 1, and at every prime the units fill the whole line. Data: computed by ch32_charts.py in the companion repository.

08.Solving Equations in a Ring

Modulo 12, the equation 4x=84x = 8 has four solutions, 2, 5, 8 and 11, while 4x=64x = 6 has none, and the right sides that can be reached are 0, 4 and 8, the multiples of gcd⁡(4,12)=4\gcd(4, 12) = 4. Modulo 13 every equation behaves. All 156 equations ax=cax = c with a≠0a \ne 0 have exactly one solution, such as x=8x = 8 for 4x=64x = 6, found by multiplying by 10, the inverse of 4.

Proof. Let aa be a unit. The element x=a−1cx = a^{-1} c is a solution, because a(a−1c)=(aa−1)c=ca(a^{-1} c) = (a a^{-1}) c = c. Any solution xx satisfies x=a−1(ax)=a−1cx = a^{-1}(ax) = a^{-1} c, so there is only one. Now let aa be a zero divisor, with ab=0ab = 0 for some b≠0b \ne 0. If ax0=ca x_0 = c, then a(x0+b)=ax0+ab=ca(x_0 + b) = a x_0 + ab = c, and x0+b≠x0x_0 + b \ne x_0, so cc has a second solution. The map x↦axx \mapsto ax therefore sends two inputs to one output, so on a finite set it cannot reach every element, and some cc has no solution at all. ■\blacksquare

Matrices and Elimination over Finite Fields solved linear systems by scaling each pivot row by the inverse of its pivot, which needs every pivot to be a unit. Over Z256\mathbb{Z}_{256} a pivot of 2 could not be scaled away, and a solution, when one existed, would not be unique. A Reed–Solomon decoder finds each error value by solving equations of this kind, and two candidates would leave it unable to choose, so byte-wide Reed–Solomon codes compute in a field with 256 elements, never in Z256\mathbb{Z}_{256} [5].

09.Integral Domains

Modulo 6, 2⋅3≡0≡2⋅02 \cdot 3 \equiv 0 \equiv 2 \cdot 0 with 3≠03 \ne 0, so the factor 2 cannot be cancelled from the two sides. Modulo 13, 4x=4y4x = 4y forces x=yx = y, by multiplying both sides by 10. The difference is the presence of zero divisors.

Proof. In an integral domain, ab=acab = ac gives a(b−c)=ab−ac=0a(b - c) = ab - ac = 0, and since a≠0a \ne 0 the factor b−cb - c must be 00, so b=cb = c. Conversely, suppose cancellation holds and ab=0ab = 0 with a≠0a \ne 0. Then ab=a0ab = a0 by the lemma on zero, and cancelling aa gives b=0b = 0, so there are no zero divisors. ■\blacksquare

The integers are an integral domain, and so is every polynomial ring built on one. Over GF(2)\mathrm{GF}(2), the product (x2+x+1)(x+1)=x3+1(x^2 + x + 1)(x + 1) = x^3 + 1 has degree 2+12 + 1, and the script finds the same law in all 3,969 pairs of nonzero polynomials over GF(2)\mathrm{GF}(2) of degree below 6. Over Z4\mathbb{Z}_4 the law breaks, since (2x)(2x)=4x2=0(2x)(2x) = 4x^2 = 0.

deg⁡(fg)=deg⁡f+deg⁡g\deg(fg) = \deg f + \deg g
(4)

Proof. Write f=amxm+⋯f = a_m x^m + \cdots and g=bkxk+⋯g = b_k x^k + \cdots with leading coefficients am≠0a_m \ne 0 and bk≠0b_k \ne 0. Every term of fgfg is a product aibjxi+ja_i b_j x^{i + j} with i≤mi \le m and j≤kj \le k, so no power above xm+kx^{m + k} appears, and the only product that reaches xm+kx^{m + k} is ambkxm+ka_m b_k x^{m + k}. Since RR has no zero divisors, ambk≠0a_m b_k \ne 0, so fgfg is nonzero of degree m+km + k. A product of nonzero polynomials is therefore nonzero, and R[x]R[x] inherits commutativity and 1≠01 \ne 0 from RR. ■\blacksquare

Proof. If fg=1fg = 1, then deg⁡f+deg⁡g=deg⁡1=0\deg f + \deg g = \deg 1 = 0 by the theorem, so both have degree 0 and are constants whose product in RR is 1. Conversely a constant that is a unit of RR keeps its inverse in R[x]R[x]. In a field every nonzero constant is a unit. ■\blacksquare

Over GF(2)\mathrm{GF}(2) the only unit is the polynomial 1, and among the 3,969 pairs the script finds (1,1)(1, 1) as the only pair with product 1. Over Z4\mathbb{Z}_4, where the corollary does not apply, (2x+1)2=4x2+4x+1=1(2x + 1)^2 = 4x^2 + 4x + 1 = 1, so 2x+12x + 1 is a unit of degree 1. Polynomials over a Field leans on the corollary at every step, because a polynomial factors in essentially one way only when the units are just the constants.

10.Fields as Rings

Modulo 13, every nonzero row of the multiplication table holds a 1, and the script confirms that every nonzero residue has an inverse. Modulo 4, the row of 2 reads 0, 2, 0, 2 and holds no 1, because 2⋅2=4≡02 \cdot 2 = 4 \equiv 0.

This restates the field of Integers and Modular Arithmetic and of Vector Spaces over Finite Fields. The ring axioms supply the laws of arithmetic and the last clause supplies division, so the nonzero elements of a field form a group under multiplication.

Proof. A field is commutative with 1≠01 \ne 0. Each nonzero element is a unit, and by Lemma: A unit is never a zero divisor, no unit is a zero divisor, so the field has none. ■\blacksquare

Proof. By Theorem: Units and zero divisors in a finite ring, each nonzero element of a finite commutative ring is a unit or a zero divisor. An integral domain has no zero divisors, so every nonzero element is a unit. ■\blacksquare

Finiteness cannot be dropped, since in the integral domain Z\mathbb{Z} the element 2 has no inverse. Together the two theorems reprove a familiar fact.

Proof. If nn is composite, write n=rsn = rs with 1<r,s<n1 < r, s < n. Then rr and ss are nonzero in Zn\mathbb{Z}_n while rs≡0rs \equiv 0, so Zn\mathbb{Z}_n has a zero divisor. It is not an integral domain, and so not a field, since every field is one. If n=pn = p is prime, Zp\mathbb{Z}_p is commutative with 1≠01 \ne 0. Suppose ab≡0(modp)ab \equiv 0 \pmod{p}. Then pp divides abab, and Euclid's lemma, Corollary: Dividing a product in Integers and Modular Arithmetic, says that pp divides aa or bb, so a≡0a \equiv 0 or b≡0b \equiv 0. Thus Zp\mathbb{Z}_p is a finite integral domain and therefore a field. ■\blacksquare

This is a second proof of Theorem: When modular arithmetic forms a field, in Integers and Modular Arithmetic. The first proof produced an inverse for each nonzero residue. This one shows only that no product of nonzero residues vanishes, and the counting argument of the finite-ring theorem supplies the inverses. The companion script confirms both verdicts for every nn from 2 to 64.

Three rings have four elements, and Figure 4 sets their tables side by side. In Z4\mathbb{Z}_4 the units are 1 and 3, and 2 is a zero divisor, since 2⋅2=02 \cdot 2 = 0. Among the 2-bit words, 01∧10=0001 \wedge 10 = 00. The third ring, on the symbols 0,1,a,b0, 1, a, b, has no zero product at all.

Multiplication and addition tables of the three rings with four elements integers mod 4 2 times 2 is 0 x 0 0 1 1 2 2 3 3 0 0 0 0 0 1 2 3 0 2 0 2 0 3 2 1 + 0 0 1 1 2 2 3 3 0 1 2 3 1 2 3 0 2 3 0 1 3 0 1 2 2-bit words, XOR and AND 01 AND 10 is 00 x 00 00 01 01 10 10 11 11 00 00 00 00 00 01 00 01 00 00 10 10 00 01 10 11 + 00 00 01 01 10 10 11 11 00 01 10 11 01 00 11 10 10 11 00 01 11 10 01 00 the four-element field no zero product x 0 0 1 1 a a b b 0 0 0 0 0 1 a b 0 a b 1 0 b 1 a + 0 0 1 1 a a b b 0 1 a b 1 0 b a a b 0 1 b a 1 0 product equal to the ring's 1 product 0 of nonzero factors sum 0: the row and the column are negatives of each other In the two right-hand rings every element is its own negative, so 1 + 1 = 0.
Figure 4. Multiplication and addition tables of the three rings with four elements. Only the four-element field has no product of nonzero elements equal to 0, and in the two right-hand rings every element is its own negative. Data: computed by ch32_charts.py in the companion repository.

Constructing Galois Fields builds the four-element field from a polynomial, and here its tables, Table 2 and Table 3, are simply given as data. Call this field F4F_4. Its products are a⋅a=ba \cdot a = b, a⋅b=1a \cdot b = 1 and b⋅b=ab \cdot b = a, so 1−1=11^{-1} = 1, a−1=ba^{-1} = b and b−1=ab^{-1} = a, and every nonzero element is a unit. Written as 01, 10 and 11, the elements 1, aa and bb add by XOR, since 1+a=b1 + a = b, a+b=1a + b = 1 and 1+b=a1 + b = a. So F4F_4 and the 2-bit words share an addition and differ only in multiplication, and that difference alone decides whether division works.

Table 2. Addition in the four-element field , where every element is its own negative

++0011aabb
000011aabb
111100bbaa
aaaabb0011
bbbbaa1100

Table 3. Multiplication in the four-element field , where every nonzero row holds exactly one 1

⋅\cdot0011aabb
0000000000
110011aabb
aa00aabb11
bb00bb11aa

Figure 5 sorts every ring of the chapter into nested families. The fields sit inside the integral domains, which sit inside the commutative rings, and the matrices stand outside on their own because their multiplication does not commute.

The rings of the chapter sorted into nested families. The outer box holds all rings. Inside it, the box of commutative rings with 1 not equal to 0 holds the integers mod 256, mod 12 and mod 4, the n-bit words under XOR and AND, and the polynomials with coefficients mod 4, all of which have zero divisors. Inside that, the box of integral domains holds the integers and the polynomials over the integers and over GF(2), all infinite. Inside that, the box of fields holds GF(2), the integers mod 13 and the four-element field. Outside the commutative box sit the 2 by 2 matrices over GF(2), a ring of 16 elements with 6 units in which AB differs from BA. all rings commutative rings with 1 not equal to 0 integers mod 256, mod 12 and mod 4 n-bit words under XOR and AND polynomials with coefficients mod 4 zero divisors live here: 2 times 128 is 0 mod 256 integral domains: no zero divisors the integers polynomials over the integers, polynomials over GF(2) every one listed here is infinite: a finite domain is a field fields: every nonzero element is a unit GF(2) and the integers mod 13 the four-element field on 0, 1, a, b a finite one has a prime power of elements not commutative 2 by 2 matrices over GF(2) AB differs from BA 16 elements, 6 units
Figure 5. The rings of the chapter sorted into nested families. Every field is an integral domain, every finite integral domain is a field, and the matrix ring falls outside the commutative rings altogether.

11.Characteristic

Adding 1 to itself modulo 12 reaches 0 after 12 copies, and in F4F_4 after 2, since 1+1=01 + 1 = 0. In the 8-bit words, 11111111⊕11111111=0000000011111111 \oplus 11111111 = 00000000, so two copies of the one suffice there too. The integers never return to 0 however many copies are added.

Table 4 collects the characteristic and the other verdicts of this chapter for the eight finite rings the script tests. The integers modulo nn have characteristic nn, and the two rings of words, the matrices and F4F_4 all have characteristic 2.

Table 4. The eight finite rings of the chapter with their counts of units and zero divisors, whether each is an integral domain or a field, and its characteristic

RingElementsUnitsZero divisorsDomainFieldCharacteristic
Z4\mathbb{Z}_4421nono4
Z12\mathbb{Z}_{12}1247nono12
Z13\mathbb{Z}_{13}13120yesyes13
Z256\mathbb{Z}_{256}256128127nono256
2-bit words412nono2
8-bit words2561254nono2
M2(GF(2))M_2(\mathrm{GF}(2))1669nono2
F4F_4430yesyes2

Proof. By the distributive law, n⋅a=a+⋯+a=1a+⋯+1a=(1+⋯+1)a=(n⋅1)a=0a=0n \cdot a = a + \cdots + a = 1a + \cdots + 1a = (1 + \cdots + 1) a = (n \cdot 1) a = 0a = 0, with nn terms in each sum and the last step from the lemma on zero. ■\blacksquare

In characteristic 2 the lemma gives a+a=0a + a = 0, so −a=a-a = a and subtraction is the same operation as addition. The script confirms f+f=0f + f = 0 for every polynomial over GF(2)\mathrm{GF}(2) of degree below 6.

Proof. Let the characteristic be n≥1n \ge 1. Then n≠1n \ne 1, because 1⋅1=1≠01 \cdot 1 = 1 \ne 0. Suppose n=rsn = rs with 1<r,s<n1 < r, s < n. Distributing, (r⋅1)(s⋅1)(r \cdot 1)(s \cdot 1) is a sum of rsrs products of 1 with 1, each equal to 1, so it is n⋅1=0n \cdot 1 = 0. An integral domain has no zero divisors, so r⋅1=0r \cdot 1 = 0 or s⋅1=0s \cdot 1 = 0, and either one contradicts the choice of nn as least. So nn is prime. In a finite ring the elements 1⋅1,2⋅1,3⋅1,…1 \cdot 1, 2 \cdot 1, 3 \cdot 1, \ldots cannot all differ, so i⋅1=j⋅1i \cdot 1 = j \cdot 1 for some i<ji < j, and then (j−i)⋅1=0(j - i) \cdot 1 = 0, which makes the characteristic positive. A finite field is an integral domain, so its characteristic is a prime. ■\blacksquare

For every nn from 2 to 64 the script computes the characteristic of Zn\mathbb{Z}_n, finds it equal to nn, and confirms that it is prime whenever Zn\mathbb{Z}_n is an integral domain. The converse fails, since the 8-bit words have the prime characteristic 2 and 254 zero divisors.

12.Characteristic Two in Hardware

Add the 4-bit words 0111 and 0001 as integers. Bit 0 gives 1+11 + 1, which writes 0 and carries 1, and the carry runs on through bits 1 and 2. The carries out of bits 0 to 3 are 1, 1, 1 and 0, and the sum is 1000. In characteristic 2 the same words give 0111⊕0001=01100111 \oplus 0001 = 0110, with no carry anywhere.

Two ways to add 4-bit words, both on the inputs a = 0111 and b = 0001. At the top, addition in characteristic 2: four XOR gates, drawn in the distinctive shape of ANSI/IEEE Std 91-1984, each take one bit of a and the same bit of b and give one sum bit, so the result 0110 has no wire between columns and settles after one gate delay. At the bottom, addition of integers modulo 16: four full-adder blocks in a ripple-carry chain, where the carries c1, c2 and c3 are all 1 and pass from block to block, giving 1000 with the carry out of bit 3 dropped. characteristic 2: four XOR gates and no carry a3 b3 0 0 s3 0 a2 b2 1 0 s2 1 a1 b1 1 0 s1 1 a0 b0 1 1 s0 0 0111 + 0001 = 0110. No wire joins two columns, so every bit settles after one gate delay. integers mod 16: a ripple-carry adder a3 b3 0 0 FA s3 1 a2 b2 1 0 FA s2 0 a1 b1 1 0 FA s1 0 a0 b0 1 1 FA s0 0 c0=0 c1=1 c2=1 c3=1 c4=0 dropped 0111 + 0001 = 1000. Bit 3 is right only after the carry has rippled through all four blocks.
Figure 6. Adding two 4-bit words in characteristic 2 takes four independent XOR gates, while adding them as integers modulo 16 takes a ripple-carry chain whose last sum bit waits for every carry below it.

Figure 6 draws both adders. The ripple-carry adder computes each sum bit from the carry below it, so bit 3 is right only after the carry has passed every full adder, and the delay grows in proportion to the width [6]. Carry-lookahead logic shortens that chain at the cost of many more gates, and no integer adder removes the dependence of high bits on low ones.

In characteristic 2 there is no carry. Adding two mm-bit words takes mm XOR gates with no wire between columns, and the sum settles after one gate delay whatever mm is. Subtraction is the same circuit, because −a=a-a = a. A field with 2m2^m elements has characteristic 2, as How Big Can a Finite Field Be shows, so its elements fit in mm-bit words that add by XOR. Addition costs almost nothing, and the real work moves to multiplication, the subject of the multiplier chapters later in this part.

13.The Freshman's Dream

Square x3+x+1x^3 + x + 1 over the integers and the result is x6+2x4+2x3+x2+2x+1x^6 + 2x^4 + 2x^3 + x^2 + 2x + 1, because every cross term, such as x3⋅xx^3 \cdot x, arrives twice, once in each order. Over GF(2)\mathrm{GF}(2) every 2 vanishes, and the square is x6+x2+1x^6 + x^2 + 1, so the bits 1011 become 1000101. The beginner's mistake (u+v)2=u2+v2(u + v)^2 = u^2 + v^2 is true in characteristic 2, and the theorem below extends it to every prime.

Proof. The binomial coefficient satisfies Equation 5, so pp divides the product (pi)⋅i! (p−i)!\binom{p}{i} \cdot i! \, (p - i)!. Every factor of i!i! and of (p−i)!(p - i)! lies between 1 and p−1p - 1, and the prime pp divides none of them, so Euclid's lemma, Corollary: Dividing a product, applied one factor at a time shows that pp does not divide i! (p−i)!i! \, (p - i)!. Applied once more to the product of (pi)\binom{p}{i} with i! (p−i)!i! \, (p - i)!, it gives p∣(pi)p \mid \binom{p}{i}. ■\blacksquare

(pi)⋅i! (p−i)!=p!=p⋅(p−1)!\binom{p}{i} \cdot i! \, (p - i)! = p! = p \cdot (p - 1)!
(5)

For p=5p = 5 the coefficients are 1, 5, 10, 10, 5, 1, and the middle four are multiples of 5, while for the composite 4 the middle coefficient (42)=6\binom{4}{2} = 6 is not a multiple of 4. The script confirms the lemma for each of the 15 primes below 50 and finds that every composite nn from 4 to 49 fails to divide some (ni)\binom{n}{i}.

(a+b)n=∑i=0n(ni)⋅aibn−i(a + b)^n = \sum_{i = 0}^{n} \binom{n}{i} \cdot a^i b^{n - i}
(6)

Proof. For n=1n = 1 both sides equal a+ba + b. Suppose the formula holds for nn. Then (a+b)n+1=(a+b)(a+b)n(a + b)^{n + 1} = (a + b)(a + b)^n, and distributing gives ∑i(ni)⋅ai+1bn−i+∑i(ni)⋅aibn+1−i\sum_i \binom{n}{i} \cdot a^{i + 1} b^{n - i} + \sum_i \binom{n}{i} \cdot a^i b^{n + 1 - i}, where commutativity moves each factor aa or bb next to the power it joins. For each ii from 0 to n+1n + 1, the terms with aibn+1−ia^i b^{n + 1 - i} collect the coefficient (ni−1)+(ni)\binom{n}{i - 1} + \binom{n}{i}, reading (n−1)\binom{n}{-1} and (nn+1)\binom{n}{n + 1} as 0, and Pascal's rule for integers makes that (n+1i)\binom{n + 1}{i}. That is the formula for n+1n + 1. ■\blacksquare

Commutativity cannot be dropped. In the matrix ring (A+B)2=A2+AB+BA+B2(A + B)^2 = A^2 + AB + BA + B^2, and since the gallery showed AB≠BAAB \ne BA, the two middle terms do not combine into 2AB2AB.

Proof. Expand (a+b)p(a + b)^p by the binomial theorem. For 0<i<p0 < i < p the lemma gives (pi)=pt\binom{p}{i} = pt for some whole number tt, so (pi)⋅aibp−i=t⋅(p⋅aibp−i)\binom{p}{i} \cdot a^i b^{p - i} = t \cdot (p \cdot a^i b^{p - i}), which is t⋅0=0t \cdot 0 = 0 because the characteristic annihilates every element. Only the terms i=0i = 0 and i=pi = p survive, and they are bpb^p and apa^p. ■\blacksquare

The script confirms the identity in Zp\mathbb{Z}_p for every prime pp below 50, in F4F_4 for all 16 pairs, and in GF(2)[x]\mathrm{GF}(2)[x] for all pairs of polynomials of degree below 6. The prime matters. In Z4\mathbb{Z}_4, of characteristic 4, (1+1)2=0(1 + 1)^2 = 0 while 12+12=21^2 + 1^2 = 2.

f2=∑icix2if^2 = \sum_i c_i x^{2i}
(8)

Proof. By the theorem with p=2p = 2, the square of a sum of two terms is the sum of their squares, and induction on the number of terms extends this to any finite sum, so f2=∑i(cixi)2=∑ici2x2if^2 = \sum_i (c_i x^i)^2 = \sum_i c_i^2 x^{2i}. Each coefficient is 0 or 1, and 02=00^2 = 0 and 12=11^2 = 1, so ci2=cic_i^2 = c_i. ■\blacksquare

Squaring the polynomial x cubed plus x plus 1 over GF(2) as pure wiring. The four input bits a3 a2 a1 a0 = 1011 each run on a wire to output position c6, c4, c2 and c0, and the odd outputs c5, c3 and c1 are tied to 0, so the seven output bits read 1000101, the polynomial x to the sixth plus x squared plus 1. No logic gate is needed. squaring over GF(2) is wiring 1 a3 0 a2 1 a1 1 a0 a(x) x3+ x + 1 1 c6 0 c5 0 0 c4 0 c3 0 1 c2 0 c1 0 1 c0 a(x)2 x6+ x2+ 1 No gate anywhere: output bit 2i is input bit i, and every odd output bit is tied to 0. Green wires carry a 1. The cross terms come in pairs, and 1 + 1 = 0 cancels each pair.
Figure 7. Squaring x cubed plus x plus 1 over GF(2) uses only wires. Input bit i drives output bit 2i, the odd output bits are constant 0, and the result 1000101 is x to the sixth plus x squared plus 1.

Figure 7 turns the corollary into a circuit with no gates at all. Output bit 2i2i is wired to input bit ii, every odd output bit is tied to 0, and the script confirms this spreading for every polynomial of degree below 8. In a field with 2m2^m elements the spread word has to be brought back to mm bits by a fixed network of XOR gates, whose origin Ideals and Quotient Rings explains, and the squarer stays far cheaper than a general multiplier. Primitive Elements and Field Structure studies the map a↦apa \mapsto a^p on a whole finite field.

14.How Big Can a Finite Field Be

In F4F_4 the sums of copies of 1 are only 0 and 1, since 1+1=01 + 1 = 0. Every element is c1⋅a+c0⋅1c_1 \cdot a + c_0 \cdot 1 for one choice of bits, and with the bits written as c1c0c_1 c_0, the choices 00, 01, 10 and 11 give 0,1,a0, 1, a and bb, so F4F_4 has 222^2 elements. In Z13\mathbb{Z}_{13} the 13 sums of copies of 1 already fill the whole field.

Proof. For whole numbers kk and ll, the sum of k+lk + l copies of 1 is k⋅1+l⋅1k \cdot 1 + l \cdot 1, and distributing (k⋅1)(l⋅1)(k \cdot 1)(l \cdot 1) gives klkl products of 1 with 1, each equal to 1, which is (kl)⋅1(kl) \cdot 1. In Zp\mathbb{Z}_p the sum and product are reduced modulo pp, which subtracts a multiple of pp, and p⋅1=0p \cdot 1 = 0, so the reduction changes nothing in FF. Thus ϕ\phi respects sums and products, and ϕ(1)=1\phi(1) = 1. If ϕ(k)=ϕ(l)\phi(k) = \phi(l) with 0≤l<k≤p−10 \le l < k \le p - 1, then (k−l)⋅1=0(k - l) \cdot 1 = 0 with 0<k−l<p0 < k - l < p, against the choice of pp as least, so ϕ\phi is one to one and PP has pp distinct elements. Because ϕ\phi respects both operations, PP is closed under them, −ϕ(k)=ϕ(−k)-\phi(k) = \phi(-k), and for k≠0k \ne 0 the element ϕ(k−1)\phi(k^{-1}) is an inverse of ϕ(k)\phi(k), since ϕ(k)ϕ(k−1)=ϕ(1)=1\phi(k) \phi(k^{-1}) = \phi(1) = 1. So PP is a field, and ϕ\phi matches it with Zp\mathbb{Z}_p operation for operation. ■\blacksquare

∣F∣=pm|F| = p^m
(9)

Proof. Make FF a vector space over its prime subfield PP. Vectors are the elements of FF, vectors add by the addition of FF, and a scalar from PP multiplies a vector by the multiplication of FF. Each axiom of Definition: Vector space in Vector Spaces over Finite Fields is then one of the ring axioms of FF, and PP is a copy of GF(p)\mathrm{GF}(p) by the previous theorem. Start a list with the vector 1. While some element of FF lies outside the span of the list, append it, and by Lemma: Extending an independent list the list stays independent. Each step enlarges the span and FF is finite, so the process stops at an independent list v1,…,vmv_1, \ldots, v_m that spans FF, which is a basis. Theorem: A space of dimension k has q to the k vectors, with q=pq = p, gives ∣F∣=pm|F| = p^m. ■\blacksquare

For F4F_4 the basis is 1,a1, a over {0,1}\{0, 1\}, and adding two elements adds their coordinate pairs bit by bit, which is XOR on 2-bit words. The same holds in every field with 2m2^m elements, whose elements add as mm-bit words by XOR.

The sizes from 2 to 64, sorted into primes, higher prime powers and sizes no field can have 2 3 4 22 5 6 7 8 23 9 32 10 11 12 13 14 15 16 24 17 18 19 20 21 22 23 24 25 52 26 27 33 28 29 30 31 32 25 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 72 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 26 prime: a field exists higher prime power: a field exists 6 struck out: no field From 2 to 64 there are 18 primes, 9 higher prime powers and 36 sizes no field can have.
Figure 8. The sizes from 2 to 64, sorted into primes, higher prime powers and sizes no field can have. Data: computed by ch32_charts.py in the companion repository.

Up to 32, the sizes no field can have are 6, 10, 12, 14, 15, 18, 20, 21, 22, 24, 26, 28 and 30. Figure 8 extends the sorting to 64, with 18 primes, 9 higher prime powers and 36 excluded sizes. The ring Z6\mathbb{Z}_6 has 6 elements, but no field does, and no field holds exactly the ten decimal digits. A byte, by contrast, is exactly the size of a field with 28=2562^8 = 256 elements, the arithmetic of byte-wide Reed–Solomon codes.

The theorem bounds the possible sizes from one side only, and that every prime power occurs is proved later in this part. Constructing Galois Fields builds the fields with 4, 8, 16 and 9 elements, and Primitive Elements and Field Structure shows that two finite fields of the same size differ only in the names of their elements. A paper of E. H. Moore from 1893 showed that every finite field is one of the prime-power fields that Galois had described, and the name Galois field is usually traced to that paper [7]. Coding texts such as [8] and [9] develop finite fields with codes in view.

15.Looking Ahead

The four-element field arrived here as two tables, with no hint of where its multiplication came from. The next chapter, Polynomials over a Field, supplies the material for building it. It divides polynomials with a remainder, computes greatest common divisors with Euclid's algorithm, counts the roots a polynomial can have, and names the polynomials that cannot be factored, the irreducible ones. Ideals and Quotient Rings then reduces polynomials modulo an irreducible one, as integers were reduced modulo a prime, and the result is a field, the kind every code of this part computes in.

16.Worked Examples

17.Exercises

References

  1. [1]Reed, Irving S. and Solomon, Gustave (1960). “Polynomial Codes over Certain Finite Fields.” Journal of the Society for Industrial and Applied Mathematics, 8(2), pp. 300–304. doi:10.1137/0108018
  2. [2]Bose, R. C. and Ray-Chaudhuri, D. K. (1960). “On a Class of Error Correcting Binary Group Codes.” Information and Control, 3(1), pp. 68–79. doi:10.1016/S0019-9958(60)90287-4
  3. [3]Lidl, Rudolf and Niederreiter, Harald (1996). “Finite Fields.” 2nd edition. Cambridge University Press. doi:10.1017/CBO9780511525926
  4. [4]McEliece, Robert J. (1987). “Finite Fields for Computer Scientists and Engineers.” Springer US. doi:10.1007/978-1-4613-1983-2
  5. [5]Lin, Shu and Costello, Jr., Daniel J. (2004). “Error Control Coding: Fundamentals and Applications.” 2nd edition. Pearson Prentice Hall.
  6. [6]Hennessy, John L. and Patterson, David A. (2017). “Computer Architecture: A Quantitative Approach.” 6th edition. Morgan Kaufmann. https://shop.elsevier.com/books/computer-architecture/hennessy/978-0-12-811905-1
  7. [7]Moore, E. Hastings (1893). “A Doubly-Infinite System of Simple Groups.” Bulletin of the American Mathematical Society, 3(3), pp. 73–78. doi:10.1090/S0002-9904-1893-00178-X
  8. [8]MacWilliams, F. Jessie and Sloane, Neil J. A. (1977). “The Theory of Error-Correcting Codes.” North-Holland. doi:10.1016/S0924-6509(08)X7030-8
  9. [9]Huffman, W. Cary and Pless, Vera (2003). “Fundamentals of Error-Correcting Codes.” Cambridge University Press. doi:10.1017/CBO9780511807077

— Anirban

Hardware–software at the seam where compilers meet microcode.

FeedbackBook modePaper
error-correction-codingfinite-fields