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 in characteristic , 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 keeps the low byte 1, so , and multiplying by 171 undoes multiplying by 3. The companion script checks this on all 256 bytes, and as runs over them, takes all 256 values.
The multiplier 2 behaves differently. Since and , two different bytes map to 0, and 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 , 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, , and , 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.
The words for addition come from Groups and Cosets. Addition must form an abelian group, so subtraction 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 , 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.
03.A Gallery of Rings
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 from Integers and Modular Arithmetic are the first finite examples.
Table 1. Seven rings with their size, zero, one and whether multiplication commutes
| Ring | Elements | Zero | One | Commutative |
|---|---|---|---|---|
| infinitely many | yes | |||
| 12 | yes | |||
| 256 | yes | |||
| infinitely many | yes | |||
| infinitely many | yes | |||
| 8-bit words, XOR and AND | 256 | 00000000 | 11111111 | yes |
| 16 | zero matrix | identity matrix | no |
For a commutative ring , the polynomial ring holds the polynomials with coefficients in , added coefficient by coefficient and multiplied by distributing every term over every term. The coefficients matter. Over the integers , while over each 2 vanishes and the product is , the bit string 1001. Each ring axiom for reduces to one in , because the coefficient of in is , so and share the coefficient , and the other laws follow alike. Polynomials over a Field develops division and roots.
The -bit words form a ring under XOR and AND, each bit position a separate copy of . Two facts make this ring odd, and for every byte , with for AND and for XOR.
The 2 by 2 matrices over , written , 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.
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, and . 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 , the distributive law gives . Adding to both sides leaves , and the other distributive law gives the same way. Next, , so is a negative of . The group has only one negative for each element, by Lemma: One identity and one inverse in Groups and Cosets, so . The same steps applied to give . Finally , since the negative of a negative is the element itself.
Proof. The zero is the identity of the group , which is unique by the same lemma of Groups and Cosets. If and both act as identities, then , where the first equality uses as an identity and the second uses . If , every element satisfies by the previous lemma.
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 .
05.Ring Homomorphisms
To check without redoing the multiplication, reduce every number modulo 9. The factors leave 2 and 5, and 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.
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, for every integer . Theorem: Congruence respects addition and multiplication, in Integers and Modular Arithmetic, then gives and . The sum and the product in are those integers reduced modulo , and two numbers from 0 to that are congruent are equal, so the sum of and in is and their product is . Since , . Finally means exactly that divides .
The theorem is the congruence theorem restated in the language of rings, and the companion script checks both equations for every from 2 to 12 and every and from 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 escapes exactly when 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 , and row 6 holds a 0 in column 2. Figure 1 marks both kinds of row.
Proof. If and , associativity gives .
In 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.
Proof. Take units and . Associativity gives and , so is a unit with the inverse claimed. That is closure. Multiplication is associative in , hence in . The identity 1 is a unit, since . For each unit , the equations also say that is a unit with inverse . Every group axiom holds.
Lemma: The units modulo n form a group, in Groups and Cosets, is the case , where closure needed Bezout's identity. Here closure is immediate, because comes with the inverse . In the units are the 128 odd bytes, and the inverse of 3 is 171, as the opening found.
Proof. If , then , using associativity and the lemma on zero. If , then .
The only units of the integers are and . If for integers and , then with both factors whole numbers of size at least 1, so and .
In the 8-bit words, forces every bit of to be 1, so the one, 11111111, is the only unit. Every other nonzero word has a 0 bit, so its complement is nonzero and , 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 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 to . Every output appears once, and the output 1 comes from the input 5, so 3 is a unit. Multiplication by 2 modulo 6 sends to , and the collision of the inputs 0 and 3 gives . Figure 2 draws both maps, and the next theorem shows that these are the only two possibilities.
Proof. Fix a nonzero element and consider the map from the ring to itself. Suppose first that is one to one. Then its outputs are as many as the elements of the ring, so they are all of them, and some has . Commutativity gives too, so is a unit. Suppose instead that for some . The distributive law and the lemma on signs give with , so is a zero divisor. No element is both, by Lemma: A unit is never a zero divisor.
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 is Theorem: When an inverse exists, in Integers and Modular Arithmetic. If , write . Then , and lies strictly between 0 and because , so it is a nonzero element of .
In the partner 128 serves every even byte, since . In general has units and zero divisors, which the script confirms for every from 2 to 40 and Figure 3 plots. Only a prime modulus has no zero divisor at all.
08.Solving Equations in a Ring
Modulo 12, the equation has four solutions, 2, 5, 8 and 11, while has none, and the right sides that can be reached are 0, 4 and 8, the multiples of . Modulo 13 every equation behaves. All 156 equations with have exactly one solution, such as for , found by multiplying by 10, the inverse of 4.
Proof. Let be a unit. The element is a solution, because . Any solution satisfies , so there is only one. Now let be a zero divisor, with for some . If , then , and , so has a second solution. The map therefore sends two inputs to one output, so on a finite set it cannot reach every element, and some has no solution at all.
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 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 [5].
09.Integral Domains
Modulo 6, with , so the factor 2 cannot be cancelled from the two sides. Modulo 13, forces , by multiplying both sides by 10. The difference is the presence of zero divisors.
Proof. In an integral domain, gives , and since the factor must be , so . Conversely, suppose cancellation holds and with . Then by the lemma on zero, and cancelling gives , so there are no zero divisors.
The integers are an integral domain, and so is every polynomial ring built on one. Over , the product has degree , and the script finds the same law in all 3,969 pairs of nonzero polynomials over of degree below 6. Over the law breaks, since .
Proof. Write and with leading coefficients and . Every term of is a product with and , so no power above appears, and the only product that reaches is . Since has no zero divisors, , so is nonzero of degree . A product of nonzero polynomials is therefore nonzero, and inherits commutativity and from .
Proof. If , then by the theorem, so both have degree 0 and are constants whose product in is 1. Conversely a constant that is a unit of keeps its inverse in . In a field every nonzero constant is a unit.
Over the only unit is the polynomial 1, and among the 3,969 pairs the script finds as the only pair with product 1. Over , where the corollary does not apply, , so 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 .
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 . 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.
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.
Finiteness cannot be dropped, since in the integral domain the element 2 has no inverse. Together the two theorems reprove a familiar fact.
Proof. If is composite, write with . Then and are nonzero in while , so has a zero divisor. It is not an integral domain, and so not a field, since every field is one. If is prime, is commutative with . Suppose . Then divides , and Euclid's lemma, Corollary: Dividing a product in Integers and Modular Arithmetic, says that divides or , so or . Thus is a finite integral domain and therefore a field.
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 from 2 to 64.
Three rings have four elements, and Figure 4 sets their tables side by side. In the units are 1 and 3, and 2 is a zero divisor, since . Among the 2-bit words, . The third ring, on the symbols , has no zero product at all.
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 . Its products are , and , so , and , and every nonzero element is a unit. Written as 01, 10 and 11, the elements 1, and add by XOR, since , and . So 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
Table 3. Multiplication in the four-element field , where every nonzero row holds exactly one 1
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.
11.Characteristic
Adding 1 to itself modulo 12 reaches 0 after 12 copies, and in after 2, since . In the 8-bit words, , 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 have characteristic , and the two rings of words, the matrices and 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
| Ring | Elements | Units | Zero divisors | Domain | Field | Characteristic |
|---|---|---|---|---|---|---|
| 4 | 2 | 1 | no | no | 4 | |
| 12 | 4 | 7 | no | no | 12 | |
| 13 | 12 | 0 | yes | yes | 13 | |
| 256 | 128 | 127 | no | no | 256 | |
| 2-bit words | 4 | 1 | 2 | no | no | 2 |
| 8-bit words | 256 | 1 | 254 | no | no | 2 |
| 16 | 6 | 9 | no | no | 2 | |
| 4 | 3 | 0 | yes | yes | 2 |
Proof. By the distributive law, , with terms in each sum and the last step from the lemma on zero.
In characteristic 2 the lemma gives , so and subtraction is the same operation as addition. The script confirms for every polynomial over of degree below 6.
Proof. Let the characteristic be . Then , because . Suppose with . Distributing, is a sum of products of 1 with 1, each equal to 1, so it is . An integral domain has no zero divisors, so or , and either one contradicts the choice of as least. So is prime. In a finite ring the elements cannot all differ, so for some , and then , which makes the characteristic positive. A finite field is an integral domain, so its characteristic is a prime.
For every from 2 to 64 the script computes the characteristic of , finds it equal to , and confirms that it is prime whenever 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 , 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 , with no carry anywhere.
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 -bit words takes XOR gates with no wire between columns, and the sum settles after one gate delay whatever is. Subtraction is the same circuit, because . A field with elements has characteristic 2, as How Big Can a Finite Field Be shows, so its elements fit in -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 over the integers and the result is , because every cross term, such as , arrives twice, once in each order. Over every 2 vanishes, and the square is , so the bits 1011 become 1000101. The beginner's mistake is true in characteristic 2, and the theorem below extends it to every prime.
Proof. The binomial coefficient satisfies Equation 5, so divides the product . Every factor of and of lies between 1 and , and the prime divides none of them, so Euclid's lemma, Corollary: Dividing a product, applied one factor at a time shows that does not divide . Applied once more to the product of with , it gives .
For 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 is not a multiple of 4. The script confirms the lemma for each of the 15 primes below 50 and finds that every composite from 4 to 49 fails to divide some .
Proof. For both sides equal . Suppose the formula holds for . Then , and distributing gives , where commutativity moves each factor or next to the power it joins. For each from 0 to , the terms with collect the coefficient , reading and as 0, and Pascal's rule for integers makes that . That is the formula for .
Commutativity cannot be dropped. In the matrix ring , and since the gallery showed , the two middle terms do not combine into .
Proof. Expand by the binomial theorem. For the lemma gives for some whole number , so , which is because the characteristic annihilates every element. Only the terms and survive, and they are and .
The script confirms the identity in for every prime below 50, in for all 16 pairs, and in for all pairs of polynomials of degree below 6. The prime matters. In , of characteristic 4, while .
Proof. By the theorem with , 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 . Each coefficient is 0 or 1, and and , so .
Figure 7 turns the corollary into a circuit with no gates at all. Output bit is wired to input bit , 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 elements the spread word has to be brought back to 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 on a whole finite field.
14.How Big Can a Finite Field Be
In the sums of copies of 1 are only 0 and 1, since . Every element is for one choice of bits, and with the bits written as , the choices 00, 01, 10 and 11 give and , so has elements. In the 13 sums of copies of 1 already fill the whole field.
Proof. For whole numbers and , the sum of copies of 1 is , and distributing gives products of 1 with 1, each equal to 1, which is . In the sum and product are reduced modulo , which subtracts a multiple of , and , so the reduction changes nothing in . Thus respects sums and products, and . If with , then with , against the choice of as least, so is one to one and has distinct elements. Because respects both operations, is closed under them, , and for the element is an inverse of , since . So is a field, and matches it with operation for operation.
Proof. Make a vector space over its prime subfield . Vectors are the elements of , vectors add by the addition of , and a scalar from multiplies a vector by the multiplication of . Each axiom of Definition: Vector space in Vector Spaces over Finite Fields is then one of the ring axioms of , and is a copy of by the previous theorem. Start a list with the vector 1. While some element of 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 is finite, so the process stops at an independent list that spans , which is a basis. Theorem: A space of dimension k has q to the k vectors, with , gives .
For the basis is over , 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 elements, whose elements add as -bit words by XOR.
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 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 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]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]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]Lidl, Rudolf and Niederreiter, Harald (1996). “Finite Fields.” 2nd edition. Cambridge University Press. doi:10.1017/CBO9780511525926
- [4]McEliece, Robert J. (1987). “Finite Fields for Computer Scientists and Engineers.” Springer US. doi:10.1007/978-1-4613-1983-2
- [5]Lin, Shu and Costello, Jr., Daniel J. (2004). “Error Control Coding: Fundamentals and Applications.” 2nd edition. Pearson Prentice Hall.
- [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]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]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]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.