Paper
Part IIIFinite Fields and Their Arithmetic

Polynomials over a Field

November 16, 202657 min readbeginner

Bit strings multiplied without carries are polynomials over GF(2). This chapter divides them with remainders, finds common factors with Euclid's algorithm, bounds their roots and finds the irreducible ones.

Rings and Fields, the chapter just before this one, proved that a finite field has pmp^m elements for some prime pp, and Integers and Modular Arithmetic built the field GF(p)\mathrm{GF}(p) from the integers modulo a prime. Neither built a field with 4, 8 or 256 elements, and those are the fields the codes of later parts need, Reed–Solomon codes among them, since a byte is a symbol of 8 bits. They are made from polynomials, and this chapter computes with polynomials the way Integers and Modular Arithmetic computed with integers.

Take the bit strings 1011 and 0111, the numbers 11 and 7, whose product is 77, binary 1001101. Multiply them again by shift and add, but drop every carry, so that each column keeps only its lowest bit. The answer is 110001, which is 49. Read each string as the coefficients of a polynomial, 1011 as x3+x+1x^3 + x + 1 and 0111 as x2+x+1x^2 + x + 1, and 110001 is their product x5+x4+1x^5 + x^4 + 1 with coefficients in GF(2)\mathrm{GF}(2). Lin and Costello compute with exactly these bit-string polynomials [1].

The chapter adds, multiplies and divides such polynomials over GF(2)\mathrm{GF}(2), GF(3)\mathrm{GF}(3) and GF(5)\mathrm{GF}(5), finds greatest common divisors with Euclid's algorithm, and bounds how many roots a polynomial can have. It ends by finding, by hand, every polynomial over GF(2)\mathrm{GF}(2) up to degree 5 that cannot be factored. Those irreducible polynomials are what the fields of this part are built on, and one of them fixes the wiring of every field multiplier in the book.

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

01.Multiplying Without Carries

Multiplying 1011 by 0111 by hand writes a shifted copy of 1011 for each 1 in 0111, here 1011, 10110 and 101100, and adds them. Lined up by column, the counts of ones from the sixth column down to the constant column are 1, 1, 2, 2, 2 and 1.

Integer addition turns each count into an output bit and a carry into the next column. The constant column holds one 1 and carries nothing, and the next holds two ones, so it writes 0 and carries 1. From there each column adds its count to the incoming carry. The carries out of the six columns, constant column first, are 0, 1, 1, 1, 1 and 1, the last becomes a seventh bit, and the sum is 1001101, which is 64+8+4+1=77=11⋅764 + 8 + 4 + 1 = 77 = 11 \cdot 7.

Drop the carries and each column keeps only the parity of its count, so 1, 1, 2, 2, 2, 1 become the bits 1, 1, 0, 0, 0, 1. That is 110001, the number 32+16+1=4932 + 16 + 1 = 49, the XOR of the shifted copies. Figure 1 sets the two sums side by side.

Multiplying 1011 by 0111 with carries gives 1001101, which is 77, and without carries gives 110001 One product of shifted rows, added two ways 1 0 1 1 x3+ x + 1 11 as an integer 0 1 1 1 × x2+ x + 1 7 as an integer 1 0 1 1 times 1 1 0 1 1 0 shifted once, times x 1 0 1 1 0 0 shifted twice, times x2 1 1 2 2 2 1 column counts how many 1s in each column as integers, with carries a column total of 2 or 3 sends 1 left carry in 1 1 1 1 1 0 0 sum 1 0 0 1 1 0 1 1001101 = 77 = 11 × 7 over GF(2), without carries each column total is taken mod 2 and no carry leaves any column sum 1 1 0 0 0 1 110001 = x5+ x4+ 1, or 49
Figure 1. The same three shifted rows summed with carries and without them. The integer sum couples every column to the ones below it through the carries, while the carry-less sum keeps each column's parity on its own. Data: the values are reproduced by ch33_polynomials_over_a_field.py in the companion repository.

The carry-less product has a meaning the integer one lacks. Write bit kk of a string as the coefficient of xkx^k. Multiplying x3+x+1x^3 + x + 1 by x2+x+1x^2 + x + 1 term by term gives one product xi⋅xj=xi+jx^i \cdot x^j = x^{i+j} for each pair of terms, so the coefficient of xkx^k counts the pairs with i+j=ki + j = k, which is exactly the count in column kk. With coefficients in GF(2)\mathrm{GF}(2), where 1+1=01 + 1 = 0, only the parity of that count survives, and the product is x5+x4+1x^5 + x^4 + 1.

For a designer the difference is the carry. The top bit of the integer sum depends on every column below it through the carry chain, and that chain is what makes integer adders and multipliers slow and large [2]. Each bit of the carry-less sum depends only on the partial products in its own column. GF Multiplier Architectures and GF Arithmetic in Software and ISAs return to this product as a circuit and as a processor operation.

02.Polynomials and Their Arithmetic

Over GF(2)\mathrm{GF}(2), adding x3+x+1x^3 + x + 1 and x2+x+1x^2 + x + 1 adds the coefficients of like powers. The terms xx and 11 appear in both and cancel, because 1+1=01 + 1 = 0, so the sum is x3+x2x^3 + x^2, or 1011⊕0111=11001011 \oplus 0111 = 1100 as bit strings. Larger fields follow the same rule. Over GF(3)\mathrm{GF}(3), (2x2+x+1)+(x+2)=2x2+2x(2x^2 + x + 1) + (x + 2) = 2x^2 + 2x, since 3≡03 \equiv 0, and over GF(5)\mathrm{GF}(5), (3x2+4x+2)+(2x+3)=3x2+x(3x^2 + 4x + 2) + (2x + 3) = 3x^2 + x.

Multiplication pairs every term of one factor with every term of the other. Over GF(3)\mathrm{GF}(3), the product of 2x2+x+12x^2 + x + 1 and x+2x + 2 collects 2⋅1=22 \cdot 1 = 2 in x3x^3, 2⋅2+1⋅1=52 \cdot 2 + 1 \cdot 1 = 5 in x2x^2, 1⋅2+1⋅1=31 \cdot 2 + 1 \cdot 1 = 3 in xx, and 1⋅2=21 \cdot 2 = 2 in the constant. Reducing 2, 5, 3 and 2 modulo 3 gives 2x3+2x2+22x^3 + 2x^2 + 2. Over GF(5)\mathrm{GF}(5), the product of 3x2+4x+23x^2 + 4x + 2 and 2x+32x + 3 has the sums 3⋅2=63 \cdot 2 = 6, 3⋅3+4⋅2=173 \cdot 3 + 4 \cdot 2 = 17, 4⋅3+2⋅2=164 \cdot 3 + 2 \cdot 2 = 16 and 2⋅3=62 \cdot 3 = 6, which reduce modulo 5 to x3+2x2+x+1x^3 + 2x^2 + x + 1.

The zero polynomial has no degree, so this chapter writes "r=0r = 0 or deg⁡r<deg⁡g\deg r < \deg g" wherever zero can occur. The letter xx only keeps the positions apart, a point the next section makes precise.

Here aia_i and bjb_j are the coefficients of ff and gg, and every sum is taken in FF. The product rule is a convolution, the sliding sum of products that a digital filter computes, and over GF(2)\mathrm{GF}(2) each aibja_i b_j is an AND and each sum an XOR. Rings and Fields met F[x]F[x] as a ring. The script confirms the ring axioms of GF(2)\mathrm{GF}(2), GF(3)\mathrm{GF}(3), GF(5)\mathrm{GF}(5), Z4\mathbb{Z}_4 and Z8\mathbb{Z}_8 on all triples of elements, 8, 27, 125, 64 and 512 of them.

The polynomials of degree below nn also form a vector space of dimension nn over FF, in the sense of Vector Spaces over Finite Fields, with the basis 1,x,…,xn−11, x, \ldots, x^{n-1}, so over GF(q)\mathrm{GF}(q) there are qnq^n of them. The polynomial view adds multiplication.

Under multiplication, degrees add. Rings and Fields proved this as Theorem: The degree of a product, for coefficients in any integral domain, and every field is one by Theorem: A field is an integral domain. For nonzero ff and gg in F[x]F[x] the law reads as follows.

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

If ff has degree mm and gg has degree nn, the top term of fgfg comes from one product only, ambnxm+na_m b_n x^{m+n}, and ambn≠0a_m b_n \ne 0 because a field has no zero divisors. The script checks the law on all 676 pairs of nonzero polynomials over GF(3)\mathrm{GF}(3) of degree below 3.

03.A Polynomial Is Not a Function

Evaluating a polynomial puts an element aa of FF in place of xx and computes in FF. Over GF(2)\mathrm{GF}(2), f(x)=x2+xf(x) = x^2 + x gives 0+0=00 + 0 = 0 at 0 and 1+1=01 + 1 = 0 at 1. So ff, a nonzero polynomial with the coefficient bits 110, defines the same function as the zero polynomial.

Proof. The coefficient of x2x^2 in x2+xx^2 + x is 1, so the polynomial is not zero, and the computation above gives 0 at both elements. For GF(p)\mathrm{GF}(p), the coefficient of xpx^p in xp−xx^p - x is 1, while Corollary: Fermat for every integer, in Integers and Modular Arithmetic, gives ap≡a(modp)a^p \equiv a \pmod{p} for every integer aa. So ap−a=0a^p - a = 0 for every element of GF(p)\mathrm{GF}(p). ■\blacksquare

The script finds x3−xx^3 - x zero at all three elements of GF(3)\mathrm{GF}(3) and x5−xx^5 - x zero at all five of GF(5)\mathrm{GF}(5). A count forces this. There are only 22=42^2 = 4 functions from GF(2)\mathrm{GF}(2) to itself, but 16 polynomials of degree below 4, and exactly four of them vanish at both points, namely 00, x2+xx^2 + x, x3+xx^3 + x and x3+x2x^3 + x^2, each a multiple of x2+xx^2 + x.

Codes care about the polynomial, not the function, since a codeword is sent as its coefficients. Evaluation is a tool applied to a polynomial, most visibly in the Reed–Solomon codes, which encode a message as the values of a polynomial at many points [3]. There the degree is kept below the number of points, which, as the section on roots shows, is exactly when the values determine the coefficients.

04.The Division Algorithm

Integers and Modular Arithmetic divided an integer aa by a positive nn to get a=qn+ra = qn + r with 0≤r<n0 \le r < n. A polynomial has no size, but it has a degree, and a remainder counts as small when its degree is below the divisor's. Over GF(2)\mathrm{GF}(2), divide x7+x4+x+1x^7 + x^4 + x + 1, the bit string 10010011, by x3+x+1x^3 + x + 1, the bit string 1011.

The leading term x7x^7 is x4x^4 times x3x^3, so the first quotient term is x4x^4, and subtracting x4(x3+x+1)x^4(x^3 + x + 1) XORs in 1011 shifted four places. That gives 10010011⊕10110000=10001110010011 \oplus 10110000 = 100011, the polynomial x5+x+1x^5 + x + 1. Its leading term gives the quotient term x2x^2, and 100011⊕101100=1111100011 \oplus 101100 = 1111. The quotient term 1 then gives 1111⊕1011=1001111 \oplus 1011 = 100, which is x2x^2, of degree below 3, so the division stops.

The quotient is x4+x2+1x^4 + x^2 + 1, the string 10101, and the remainder is x2x^2. Multiplying back, (x4+x2+1)(x3+x+1)=x7+x4+x2+x+1(x^4 + x^2 + 1)(x^3 + x + 1) = x^7 + x^4 + x^2 + x + 1, and adding the remainder x2x^2 restores the dividend. Figure 2 lays the steps out as integer long division, with every subtraction an XOR.

Long division of 10010011 by 1011 over GF(2), giving quotient 10101 and remainder 100 Long division over GF(2), where every subtraction is an XOR 1 0 1 0 1 quotient x4+ x2+ 1 1 0 0 1 0 0 1 1 1011 x3+ x + 1 dividend x7+ x4+ x + 1 1 0 1 1 subtract x4times 1011 0 0 1 0 0 0 1 1 XOR leaves 100011 1 0 1 1 subtract x2times 1011 0 0 1 1 1 1 XOR leaves 1111 1 0 1 1 subtract 1 times 1011 0 1 0 0 remainder 100, that is x2
Figure 2. Long division of by over . Every subtraction is an XOR of the divisor shifted under the leading 1 of what is left, and the quotient bits record which shifts were used. Data: the values are reproduced by ch33_polynomials_over_a_field.py in the companion repository.

The general statement has the same shape as the integer one.

Proof. Write m=deg⁡gm = \deg g, and let bmb_m be the leading coefficient of gg. Existence goes by induction on the degree of ff. If f=0f = 0 or deg⁡f<m\deg f < m, take q=0q = 0 and r=fr = f. Otherwise let n=deg⁡f≥mn = \deg f \ge m, with leading coefficient ana_n, and assume the claim for every polynomial of degree below nn. The polynomial anbm−1xn−mga_n b_m^{-1} x^{n-m} g has degree nn and leading coefficient anbm−1bm=ana_n b_m^{-1} b_m = a_n, so in f1=f−anbm−1xn−mgf_1 = f - a_n b_m^{-1} x^{n-m} g the terms in xnx^n cancel, and f1=0f_1 = 0 or deg⁡f1<n\deg f_1 < n. By the induction hypothesis f1=q1g+rf_1 = q_1 g + r with r=0r = 0 or deg⁡r<m\deg r < m, and then f=(q1+anbm−1xn−m)g+rf = (q_1 + a_n b_m^{-1} x^{n-m}) g + r. For uniqueness, suppose f=qg+r=q′g+r′f = qg + r = q'g + r' with both remainders satisfying the degree condition. Then (q−q′)g=r′−r(q - q')g = r' - r. If q≠q′q \ne q', the left side has degree at least mm by Equation 2, while the right side is 0 or has degree below mm, which is impossible. So q=q′q = q', and then r=r′r = r'. ■\blacksquare

The proof uses the field twice. Existence needs the inverse bm−1b_m^{-1}, and uniqueness needs deg⁡((q−q′)g)≥m\deg((q - q')g) \ge m, which holds whenever bmb_m is not a zero divisor. A monic divisor meets both needs over any commutative ring, which is why division by a monic polynomial works there too.

Over GF(5)\mathrm{GF}(5) the inverse is real work. Divide 3x3+x2+4x+23x^3 + x^2 + 4x + 2 by 2x2+3x+12x^2 + 3x + 1. The inverse of the leading coefficient 2 is 3, since 2⋅3=6≡12 \cdot 3 = 6 \equiv 1, so the first quotient term is 3⋅3 x=4x3 \cdot 3 \, x = 4x, and subtracting 4x(2x2+3x+1)=3x3+2x2+4x4x(2x^2 + 3x + 1) = 3x^3 + 2x^2 + 4x leaves 4x2+24x^2 + 2. The next quotient term is 4⋅3=12≡24 \cdot 3 = 12 \equiv 2, and subtracting 2(2x2+3x+1)=4x2+x+22(2x^2 + 3x + 1) = 4x^2 + x + 2 leaves 4x4x. Table 1 records the two steps.

Table 1. Dividing by over , where each quotient term multiplies by the inverse 3 of the leading coefficient 2

StepLeading term leftQuotient termSubtractedLeft over
first3x33x^33⋅3 x=4x3 \cdot 3 \, x = 4x3x3+2x2+4x3x^3 + 2x^2 + 4x4x2+24x^2 + 2
second4x24x^24⋅3=24 \cdot 3 = 24x2+x+24x^2 + x + 24x4x

Source: reproduced by ch33_polynomials_over_a_field.py.

The quotient is 4x+24x + 2 and the remainder is 4x4x. Indeed (4x+2)(2x2+3x+1)=8x3+16x2+10x+2=3x3+x2+2(4x + 2)(2x^2 + 3x + 1) = 8x^3 + 16x^2 + 10x + 2 = 3x^3 + x^2 + 2 over GF(5)\mathrm{GF}(5), and adding 4x4x restores the dividend. The script confirms existence and uniqueness on all 960 pairs over GF(2)\mathrm{GF}(2) with ff of degree below 6 and gg nonzero of degree below 4.

A remainder modulo a fixed polynomial behaves like a remainder modulo a fixed integer. Modulo g=x3+x+1g = x^3 + x + 1 over GF(2)\mathrm{GF}(2), x3=g+x+1x^3 = g + x + 1 leaves x+1x + 1, so x4x^4 leaves x2+xx^2 + x and x3+x2x^3 + x^2 leaves x2+x+1x^2 + x + 1. Their product x7+x6x^7 + x^6 leaves x2x^2, and so does the product of their remainders, (x2+x)(x2+x+1)=x4+x(x^2 + x)(x^2 + x + 1) = x^4 + x. Their sum x4+x3+x2x^4 + x^3 + x^2 leaves 1, and so does (x2+x)+(x2+x+1)(x^2 + x) + (x^2 + x + 1).

Proof. Write f=q1g+r1f = q_1 g + r_1 and h=q2g+r2h = q_2 g + r_2. Then f+h=(q1+q2)g+(r1+r2)f + h = (q_1 + q_2) g + (r_1 + r_2), and r1+r2r_1 + r_2 is 0 or has degree below deg⁡g\deg g, so by uniqueness it is the remainder of f+hf + h. For the product, fh=(q1q2g+q1r2+q2r1)g+r1r2fh = (q_1 q_2 g + q_1 r_2 + q_2 r_1) g + r_1 r_2. Dividing r1r2=q3g+r3r_1 r_2 = q_3 g + r_3 gives fh=(q1q2g+q1r2+q2r1+q3)g+r3fh = (q_1 q_2 g + q_1 r_2 + q_2 r_1 + q_3) g + r_3, so by uniqueness fhfh and r1r2r_1 r_2 share the remainder r3r_3. ■\blacksquare

This is the polynomial form of Theorem: Congruence respects addition and multiplication, in Integers and Modular Arithmetic, and the script checks both rules modulo x3+x+1x^3 + x + 1 on all 1,024 pairs of polynomials of degree below 5. In the language of Groups and Cosets, the multiples of gg form a subgroup of F[x]F[x] under addition, and each remainder names one of its cosets. Modulo x3+x+1x^3 + x + 1 there are eight remainders, the polynomials of degree below 3, and what they form under their own sum and product is the subject of Ideals and Quotient Rings.

05.Greatest Common Divisors and Euclid's Algorithm

Over GF(2)\mathrm{GF}(2), the polynomials x5+x4+1x^5 + x^4 + 1 and x4+x2+1x^4 + x^2 + 1 share a factor. The first is (x2+x+1)(x3+x+1)(x^2 + x + 1)(x^3 + x + 1), and the second is (x2+x+1)2(x^2 + x + 1)^2, since Corollary: Squaring spreads the bits, in Rings and Fields, squares x2+x+1x^2 + x + 1 term by term. Euclid's algorithm finds such a common factor without knowing the factorizations, exactly as it did for integers.

Associates divide each other, and over a field no other pair of nonzero polynomials does. If f∣gf \mid g and g∣fg \mid f, then g=ufg = uf and f=vgf = vg, so f(1−vu)=0f(1 - vu) = 0. Since F[x]F[x] has no zero divisors, vu=1vu = 1, and by Corollary: The units of a polynomial ring, uu and vv are nonzero constants. A nonzero ff with leading coefficient aa has exactly one monic associate, a−1fa^{-1} f, and that is how a greatest common divisor is made unique.

Greatest means greatest in the order of divisibility, so no common divisor has larger degree. Two greatest common divisors divide each other, so they are associates, and exactly one of them is monic. Euclid's algorithm shows that one exists, using one fact about a single division.

Proof. A polynomial that divides gg and rr divides qg+r=fqg + r = f. A polynomial that divides ff and gg divides f−qg=rf - qg = r. ■\blacksquare

Proof. Each ri+1r_{i+1} is 0 or has degree below deg⁡ri\deg r_i, so the nonzero remainders after r1r_1 have strictly falling degrees between 0 and deg⁡g−1\deg g - 1. There are at most deg⁡g\deg g of them, and the division after the last produces 0. Let rkr_k be the last nonzero remainder. By the lemma, applied to each division in turn, the common divisors of ff and gg are those of r1r_1 and r2r_2, then of r2r_2 and r3r_3, and finally of rkr_k and 00, which are the divisors of rkr_k. So rkr_k is a common divisor that every common divisor divides. ■\blacksquare

For integers, Integers and Modular Arithmetic needed Lemma: Remainders halve every two steps to bound the steps. Polynomials need no such lemma, since the degree falls at every step. On the pair above, dividing x5+x4+1x^5 + x^4 + 1 by x4+x2+1x^4 + x^2 + 1 gives the quotient x+1x + 1 and the remainder x3+x2+xx^3 + x^2 + x. Dividing x4+x2+1x^4 + x^2 + 1 by x3+x2+xx^3 + x^2 + x gives the quotient x+1x + 1 and the remainder x2+x+1x^2 + x + 1, which divides x3+x2+xx^3 + x^2 + x exactly xx times. The degrees run 5, 4, 3 and 2 before the remainder vanishes, and the greatest common divisor is x2+x+1x^2 + x + 1. The script runs the algorithm on all 961 pairs of nonzero polynomials over GF(2)\mathrm{GF}(2) of degree below 5 and confirms each answer against every common divisor.

06.The Extended Euclidean Algorithm

The integer algorithm carried cofactors sis_i and tit_i with ri=sia+tibr_i = s_i a + t_i b in every row, and the same columns work for polynomials. Row 0 holds r0=fr_0 = f with (s0,t0)=(1,0)(s_0, t_0) = (1, 0), row 1 holds r1=gr_1 = g with (s1,t1)=(0,1)(s_1, t_1) = (0, 1), and each later row follows from the quotient qiq_i of ri−1r_{i-1} by rir_i.

gcd⁡(f,g)=sf+tg\gcd(f, g) = s f + t g
(5)

Proof. If g=0g = 0 and aa is the leading coefficient of ff, then gcd⁡(f,g)=a−1f\gcd(f, g) = a^{-1} f, so s=a−1s = a^{-1} and t=0t = 0. Otherwise run the extended algorithm. Rows 0 and 1 satisfy ri=sif+tigr_i = s_i f + t_i g by their choice, and if rows i−1i - 1 and ii satisfy it, then Equation 4 gives ri+1=(si−1f+ti−1g)−qi(sif+tig)=si+1f+ti+1gr_{i+1} = (s_{i-1} f + t_{i-1} g) - q_i (s_i f + t_i g) = s_{i+1} f + t_{i+1} g. So every row does. The last nonzero remainder rkr_k is a greatest common divisor, and if cc is its leading coefficient, then gcd⁡(f,g)=(c−1sk)f+(c−1tk)g\gcd(f, g) = (c^{-1} s_k) f + (c^{-1} t_k) g. ■\blacksquare

Figure 3 runs the table on f=x5+x4+1f = x^5 + x^4 + 1 and g=x4+x2+1g = x^4 + x^2 + 1 over GF(2)\mathrm{GF}(2), where subtraction is addition. Row 2 takes s2=1s_2 = 1 and t2=0−(x+1)⋅1=x+1t_2 = 0 - (x + 1) \cdot 1 = x + 1, and row 3 takes s3=0−(x+1)⋅1=x+1s_3 = 0 - (x + 1) \cdot 1 = x + 1 and t3=1−(x+1)2=x2t_3 = 1 - (x + 1)^2 = x^2. Row 3 holds the greatest common divisor, and the identity reads as follows.

(x+1)(x5+x4+1)+x2(x4+x2+1)=x2+x+1(x + 1)(x^5 + x^4 + 1) + x^2 (x^4 + x^2 + 1) = x^2 + x + 1
(6)

The first product is x6+x4+x+1x^6 + x^4 + x + 1, the second is x6+x4+x2x^6 + x^4 + x^2, and their sum over GF(2)\mathrm{GF}(2) is x2+x+1x^2 + x + 1.

The extended Euclidean table for x^5 + x^4 + 1 and x^4 + x^2 + 1 over GF(2), with the gcd row boxed The extended Euclidean algorithm over GF(2) f = x5+ x4+ 1 (110001) and g = x4+ x2+ 1 (10101) i r q s t 0 x5+ x4+ 1 110001 1 1 0 0 1 x4+ x2+ 1 10101 x + 1 11 0 0 1 1 2 x3+ x2+ x 1110 x + 1 11 1 1 x + 1 11 3 x2+ x + 1 111 x 10 x + 1 11 x2 100 4 0 0 x2+ x + 1 111 x3+ x + 1 1011 (x + 1)(x5+ x4+ 1) + x2(x4+ x2+ 1) = x2+ x + 1 Row 3 holds the last nonzero remainder, the gcd, with the s and t that build it from f and g.
Figure 3. The extended Euclidean algorithm for and over . Each row is , and the boxed row gives with its cofactors. Data: computed by ch33_charts.py in the companion repository.

Over GF(3)\mathrm{GF}(3) the subtractions carry signs and the leading coefficients need inverses. Take f=x3+x2+x+1=(x+1)(x2+1)f = x^3 + x^2 + x + 1 = (x + 1)(x^2 + 1) and g=2x2+1=(x+1)(2x+1)g = 2x^2 + 1 = (x + 1)(2x + 1), though the algorithm does not need the factorizations. The inverse of 2 is 2 itself, since 2⋅2=4≡12 \cdot 2 = 4 \equiv 1. Dividing ff by gg gives the quotient 2x+22x + 2 and the remainder 2x+22x + 2, and dividing gg by 2x+22x + 2 gives the quotient x+2x + 2 and the remainder 0. Table 2 carries the cofactors.

Table 2. The extended Euclidean algorithm for and over

iirir_iqiq_isis_itit_i
0x3+x2+x+1x^3 + x^2 + x + 11100
12x2+12x^2 + 12x+22x + 20011
22x+22x + 2x+2x + 211x+1x + 1
3002x+12x + 12x2+22x^2 + 2

Source: reproduced by ch33_polynomials_over_a_field.py.

Row 2 says f+(x+1)g=2x+2f + (x + 1) g = 2x + 2, and indeed (x+1)(2x2+1)=2x3+2x2+x+1(x + 1)(2x^2 + 1) = 2x^3 + 2x^2 + x + 1, which added to ff gives 3x3+3x2+2x+2=2x+23x^3 + 3x^2 + 2x + 2 = 2x + 2. That remainder is not monic, so multiply the row by 2, the inverse of its leading coefficient. The result is 2f+(2x+2)g=x+12f + (2x + 2) g = x + 1, and gcd⁡(f,g)=x+1\gcd(f, g) = x + 1.

Bezout's identity also computes inverses. Over GF(2)\mathrm{GF}(2), look for bb with (x2+1)b mod (x3+x+1)=1(x^2 + 1) b \bmod (x^3 + x + 1) = 1 by running the table on f=x3+x+1f = x^3 + x + 1 and g=x2+1g = x^2 + 1. The first division, x3+x+1=x(x2+1)+1x^3 + x + 1 = x(x^2 + 1) + 1, already leaves 1, as Table 3 shows.

Table 3. The extended Euclidean algorithm for and over , which finds the inverse of

iirir_iqiq_isis_itit_i
0x3+x+1x^3 + x + 11100
1x2+1x^2 + 1xx0011
211x2+1x^2 + 111xx
300x2+1x^2 + 1x3+x+1x^3 + x + 1

Source: reproduced by ch33_polynomials_over_a_field.py.

Row 2 reads 1=1⋅(x3+x+1)+x(x2+1)1 = 1 \cdot (x^3 + x + 1) + x (x^2 + 1), and taking remainders modulo x3+x+1x^3 + x + 1 removes the first term. So the inverse of x2+1x^2 + 1 is xx, and directly x(x2+1)=x3+x=(x3+x+1)+1x(x^2 + 1) = x^3 + x = (x^3 + x + 1) + 1. In general, when gcd⁡(f,g)=1\gcd(f, g) = 1 the last nonzero remainder is a nonzero constant cc, and c−1c^{-1} times its tt entry is the inverse of gg modulo ff, the scaling the proof of Bezout's identity uses. Over GF(2)\mathrm{GF}(2) the constant is 1. Over GF(3)\mathrm{GF}(3), the table for f=x2+1f = x^2 + 1 and g=x+1g = x + 1 stops at r2=2r_2 = 2 with t2=2x+1t_2 = 2x + 1, so the inverse of x+1x + 1 is 2(2x+1)=x+22(2x + 1) = x + 2, and indeed (x+1)(x+2)=x2+2=(x2+1)+1(x + 1)(x + 2) = x^2 + 2 = (x^2 + 1) + 1. Why every nonzero remainder modulo an irreducible polynomial has such an inverse is explained in Ideals and Quotient Rings.

07.Roots and Factors

Over GF(5)\mathrm{GF}(5), the polynomial f(x)=x3+2x+1f(x) = x^3 + 2x + 1 takes the value 8+4+1=13≡38 + 4 + 1 = 13 \equiv 3 at 2. Dividing ff by x−2x - 2, which over GF(5)\mathrm{GF}(5) is x+3x + 3, gives the quotient x2+2x+1x^2 + 2x + 1 and the remainder 3, the same number.

f(x)=q(x)(x−a)+f(a)f(x) = q(x)(x - a) + f(a)
(7)

Proof. The divisor x−ax - a has degree 1, so the division algorithm gives f=q⋅(x−a)+rf = q \cdot (x - a) + r with rr a constant. Substituting aa for xx respects sums and products, because FF is commutative, so it is a ring homomorphism from F[x]F[x] to FF in the sense of Rings and Fields. Hence f(a)=q(a)(a−a)+r=rf(a) = q(a)(a - a) + r = r. ■\blacksquare

Proof. If f(a)=0f(a) = 0, then Equation 7 reads f=q⋅(x−a)f = q \cdot (x - a). If f=h⋅(x−a)f = h \cdot (x - a), then the remainder of ff by x−ax - a is 0, and by the theorem it equals f(a)f(a). ■\blacksquare

The script checks the remainder theorem on all 625 polynomials over GF(5)\mathrm{GF}(5) of degree below 4, at all five points. Since each root contributes a factor, roots cannot outnumber the degree.

Proof. Induction on nn. A polynomial of degree 0 is a nonzero constant and has no roots. Let n≥1n \ge 1, and suppose ff has a root aa, since otherwise there is nothing to prove. Then f=(x−a)qf = (x - a) q by the factor theorem, with deg⁡q=n−1\deg q = n - 1 by Equation 2. If b≠ab \ne a is another root, then 0=f(b)=(b−a)q(b)0 = f(b) = (b - a) q(b), and since b−a≠0b - a \ne 0 and a field has no zero divisors, q(b)=0q(b) = 0. So every other root is one of the at most n−1n - 1 roots of qq, and ff has at most nn. ■\blacksquare

The bound can be met. Over GF(5)\mathrm{GF}(5), x4−1x^4 - 1 has the four roots 1, 2, 3 and 4 by Theorem: Fermat's little theorem, and so it is (x−1)(x−2)(x−3)(x−4)(x - 1)(x - 2)(x - 3)(x - 4). Among the 625 polynomials of degree below 4, the script finds no nonzero one with more roots than its degree.

Proof. Their difference is zero or has degree below kk, and it has at least kk roots, so by the theorem it is zero. ■\blacksquare

This is the condition the section on functions promised. A polynomial over GF(q)\mathrm{GF}(q) of degree below qq is fixed by its function, while x2+xx^2 + x over GF(2)\mathrm{GF}(2) has degree 2, not below 2, so it can share the zero function. Reed–Solomon codes keep the degree below the number of evaluation points for exactly this reason. Over GF(2)\mathrm{GF}(2), both possible roots can be read straight off the bits.

Proof. Substituting 0 kills every term with a positive power of xx, so f(0)f(0) is the constant term. Substituting 1 turns every term xkx^k into 1, so f(1)f(1) is the number of nonzero terms reduced modulo 2. ■\blacksquare

By the factor theorem, xx divides a polynomial over GF(2)\mathrm{GF}(2) exactly when its last bit is 0, and x+1x + 1 divides it exactly when its weight, the number of 1 bits, is even. The second rule is even-weight parity in a new language. The words of Example: The even-weight code of length 4, in Linear Codes, are the polynomials of degree below 4 with f(1)=0f(1) = 0, which are the multiples of x+1x + 1 among them, such as x3+x2+x+1=(x+1)3x^3 + x^2 + x + 1 = (x + 1)^3 with weight 4. In hardware, f(1)f(1) is the XOR of all the bits, the parity tree of every checker in Linear Block Codes, and f(0)f(0) is a single wire.

08.Irreducible Polynomials

Over GF(2)\mathrm{GF}(2), the polynomial x2+x+1x^2 + x + 1 takes the value 1 at both 0 and 1, so it has no root. A factorization would need two factors of degree 1, and a factor x−ax - a would make aa a root, so x2+x+1x^2 + x + 1 cannot be factored at all. Polynomials like it play the part of the primes.

The only divisors of an irreducible ff are the nonzero constants and the associates of ff, and every polynomial of degree 1 is irreducible. The field matters. Over GF(3)\mathrm{GF}(3), x2+1x^2 + 1 takes the values 1, 2 and 2 at 0, 1 and 2, so it is irreducible there, while over GF(2)\mathrm{GF}(2) it is (x+1)2(x + 1)^2.

Proof. If ff has a root aa, then f=(x−a)qf = (x - a) q with deg⁡q=deg⁡f−1≥1\deg q = \deg f - 1 \ge 1, so ff is reducible. Conversely, if f=ghf = gh with both degrees at least 1, the degrees add to 2 or 3, so one factor has degree 1, say g=cx+dg = cx + d with c≠0c \ne 0. Then a=−dc−1a = -d c^{-1} gives f(a)=g(a)h(a)=0f(a) = g(a) h(a) = 0. ■\blacksquare

The script confirms the test for every monic polynomial of degree 2 and 3 over GF(2)\mathrm{GF}(2), GF(3)\mathrm{GF}(3) and GF(5)\mathrm{GF}(5), which covers the rest, since a nonzero constant factor changes neither the roots nor irreducibility.

That trial division can stop early. A reducible ff of degree dd is ghgh with both degrees at least 1, so the smaller factor has degree at most ⌊d/2⌋\lfloor d/2 \rfloor, and a divisor of it of least positive degree is irreducible. So ff is irreducible exactly when no irreducible polynomial of degree at most ⌊d/2⌋\lfloor d/2 \rfloor divides it.

These tests, with the rules for the roots 0 and 1, find every irreducible polynomial over GF(2)\mathrm{GF}(2) up to degree 5 by hand. Above degree 1 a candidate must end in 1 and have an odd number of terms. In degree 1, both xx and x+1x + 1 are irreducible. In degree 2 only 111, which is x2+x+1x^2 + x + 1, survives. In degree 3, 1011 and 1101 survive, the polynomials x3+x+1x^3 + x + 1 and x3+x2+1x^3 + x^2 + 1, both irreducible by the root test.

In degree 4, a rootless candidate that is reducible has only factors of degree 2, so it is (x2+x+1)2(x^2 + x + 1)^2, the string 10101, and of 10011, 10101, 11001 and 11111 three remain. In degree 5 there are eight rootless candidates, and a reducible one is x2+x+1x^2 + x + 1 times a rootless cubic, giving (x2+x+1)(x3+x+1)=x5+x4+1(x^2 + x + 1)(x^3 + x + 1) = x^5 + x^4 + 1 and (x2+x+1)(x3+x2+1)=x5+x+1(x^2 + x + 1)(x^3 + x^2 + 1) = x^5 + x + 1. Six remain. Table 4 collects the results.

Table 4. Every irreducible polynomial over of degree 1 to 5, written as bit strings with the leading coefficient on the left

DegreeCountIrreducible polynomials
1210, 11
21111
321011, 1101
4310011, 11001, 11111
56100101, 101001, 101111, 110111, 111011, 111101

Source: reproduced by ch33_polynomials_over_a_field.py.

So 10011 is x4+x+1x^4 + x + 1, 11001 is x4+x3+1x^4 + x^3 + 1, and 100101 is x5+x2+1x^5 + x^2 + 1. The script finds the same lists by trial division and by a sieve, the polynomial form of the sieve of Eratosthenes. List every polynomial of degree 1 to DD, take each irreducible in turn, and cross out its products with every polynomial of degree at least 1. A reducible polynomial falls to any of its irreducible factors, so what survives is irreducible, and only factors of degree up to ⌊D/2⌋\lfloor D/2 \rfloor are needed. Over GF(2)\mathrm{GF}(2), with a polynomial stored as an integer whose bits are its coefficients and the product carry-less, the companion script writes it in a few lines.

Python
def sieve2(top):
limit = 1 << (top + 1)
crossed = [False] * limit
for a in range(2, limit):
if crossed[a] or 2 * deg2(a) > top:
continue
for b in range(2, 1 << (top - deg2(a) + 1)):
crossed[clmul(a, b)] = True
return [a for a in range(2, limit) if not crossed[a]]

The outer loop meets the polynomials in increasing order, so each uncrossed one it reaches is irreducible, since any smaller irreducible factor would already have crossed it out, and the inner loop crosses out its products with every bb of degree at least 1 that stay within the top degree. Figure 4 shows the sieve up to degree 5. In degree 4, eight of the 16 polynomials fall to xx, four more to x+1x + 1, one to x2+x+1x^2 + x + 1, and three survive. In degree 5 the numbers are 16, 8, 2 and 6.

A sieve that strikes out the multiples of x, x + 1 and x^2 + x + 1 among the polynomials over GF(2) of degree 1 to 5 A sieve for the irreducible polynomials over GF(2) of degree 1 to 5 Past degree 1 a constant term 0 means a factor x, so only constant term 1 is shown. degree 1 2 kept 10 11 degree 2 1 kept 101 111 degree 3 2 kept 1001 1011 1101 1111 degree 4 3 kept 10001 10011 10101 10111 11001 11011 11101 11111 degree 5 6 kept 100001 100011 100101 100111 101001 101011 101101 101111 110001 110011 110101 110111 111001 111011 111101 111111 multiple of x + 1 (even weight) multiple of x2+ x + 1 irreducible The survivors number 2, 1, 2, 3 and 6 for degrees 1 to 5.
Figure 4. The sieve over up to degree 5. Multiples of end in 0, multiples of have an even number of ones, and only , and need the factor to remove them. Data: computed by ch33_charts.py in the companion repository.

Run to degree 10, the sieve gives the counts 9, 18, 30, 56 and 99 for degrees 6 to 10. Figure 5 plots them against the 2m2^m polynomials of each degree mm, beside the curve 2m/m2^m / m, which they track closely. At degree 10, 99 of the 1,024 polynomials are irreducible, and 10⋅99/1024=0.96710 \cdot 99 / 1024 = 0.967, so close to one polynomial in mm of degree mm is irreducible. Irreducible Polynomials and Root Finding counts them exactly and gives tests far faster than trial division.

The number of irreducible polynomials over GF(2) of each degree from 1 to 10 on a doubling scale, against 2^m and 2^m / m 1 4 16 64 256 1024 1 2 3 4 5 6 7 8 9 10 m, the degree how many (doubling scale) 2 1 2 3 6 9 18 30 56 99 at degree 10, 99 of the 1024 are irreducible, and 10 × 99 / 1024 = 0.967 all 2mof degree m irreducible ones, I(m) 2m/ m
Figure 5. The number of irreducible polynomials over of degree , against all polynomials of that degree and the curve . Data: computed by ch33_charts.py in the companion repository.

The same search works over GF(3)\mathrm{GF}(3). A monic quadratic x2+bx+cx^2 + bx + c has 9 choices of bb and cc, and by the root test it is reducible exactly when it is (x−a)(x−a′)(x - a)(x - a') with a≤a′a \le a' among 0, 1 and 2. That gives three squares and three products of distinct factors, and the six are different, since their sets of roots differ. So 6 of the 9 split, and the other 3 are irreducible, namely x2+1x^2 + 1, x2+x+2x^2 + x + 2 and x2+2x+2x^2 + 2x + 2. For instance x2+x+2x^2 + x + 2 takes the values 2, 1 and 2 at 0, 1 and 2.

09.Unique Factorization

Every integer above 1 is a product of primes in one way only, and the step that proves it is Euclid's lemma, Corollary: Dividing a product in Integers and Modular Arithmetic. Polynomials over a field factor into irreducibles in one way only, and the key step is the same. Over GF(2)\mathrm{GF}(2), for instance, x5+x4+1=(x2+x+1)(x3+x+1)x^5 + x^4 + 1 = (x^2 + x + 1)(x^3 + x + 1) has no other factorization into irreducibles.

Proof. Suppose pp does not divide aa. The monic gcd⁡(p,a)\gcd(p, a) divides pp, so it is 1 or the monic associate of pp, and the second would make pp divide aa. So gcd⁡(p,a)=1\gcd(p, a) = 1, and Bezout's identity gives 1=sp+ta1 = sp + ta. Multiplying by bb gives b=spb+t(ab)b = spb + t(ab), and pp divides both terms on the right, so p∣bp \mid b. ■\blacksquare

The script checks the lemma for the five irreducibles of degree at most 3 over GF(2)\mathrm{GF}(2) against every pair of nonzero aa and bb of degree below 4, 1,125 triples in all. Irreducibility is essential, since x2+1=(x+1)2x^2 + 1 = (x + 1)^2 divides (x+1)(x+1)(x + 1)(x + 1) but neither factor.

f=c p1p2⋯pkf = c \, p_1 p_2 \cdots p_k
(8)

Proof. Existence goes by induction on deg⁡f\deg f. If ff is irreducible, then f=c⋅(c−1f)f = c \cdot (c^{-1} f) with c−1fc^{-1} f monic and irreducible. Otherwise f=ghf = gh with both of lower degree, the hypothesis factors each, and comparing leading coefficients shows the constant in front is cc. For uniqueness, suppose c p1⋯pk=c p1′⋯pl′c \, p_1 \cdots p_k = c \, p'_1 \cdots p'_l. Then p1p_1 divides p1′⋯pl′p'_1 \cdots p'_l, so by the lemma, applied repeatedly, it divides some pj′p'_j. Since pj′p'_j is irreducible and deg⁡p1≥1\deg p_1 \ge 1, the two are associates, and both are monic, so p1=pj′p_1 = p'_j. Cancelling it, which is allowed because F[x]F[x] has no zero divisors, leaves two factorizations of a polynomial of lower degree. If one side is now the constant cc, comparing degrees shows that the other has no factors left either. Otherwise both agree by induction. ■\blacksquare

Over GF(2)\mathrm{GF}(2) every nonzero polynomial is monic, so c=1c = 1. The script builds every product of irreducibles of total degree at most 6, 126 products in all, and finds each of the 2+4+8+16+32+64=1262 + 4 + 8 + 16 + 32 + 64 = 126 polynomials of degree 1 to 6 exactly once.

For example, x4+1=(x+1)4x^4 + 1 = (x + 1)^4 by the freshman's dream, and x5+1=(x+1)(x4+x3+x2+x+1)x^5 + 1 = (x + 1)(x^4 + x^3 + x^2 + x + 1), since every middle term of the product appears twice and cancels. The quartic is 11111, irreducible by the table. Polynomials xn+1x^n + 1 factor in patterns that Minimal Polynomials and Cyclotomic Cosets explains in general.

10.Polynomial Arithmetic in Hardware

Every operation of this chapter over GF(2)\mathrm{GF}(2) is a small circuit. Adding two polynomials of degree below mm takes mm XOR gates side by side, with no wire between neighbors. Multiplying them forms the m2m^2 partial products aibja_i b_j with AND gates and sums each column with XOR gates. Column kk holds the products with i+j=ki + j = k, so for m=3m = 3 the five columns hold 1, 2, 3, 2 and 1 products. A column of nn terms needs n−1n - 1 XOR gates, so the 2m−12m - 1 columns need m2−(2m−1)=(m−1)2m^2 - (2m - 1) = (m - 1)^2. For 3-bit operands that is 3 XOR gates for the adder and 9 AND gates and 4 XOR gates for the multiplier, as Figure 6 draws, and for 8-bit operands 8, 64 and 49.

A row of three XOR gates adds two polynomials over GF(2), and nine AND gates feeding XOR trees multiply them Addition, one XOR gate per bit and no carry chain a2 b2 s2 a1 b1 s1 a0 b0 s0 Each sum bit reads only its own column, so 3-bit operands need 3 gates and 8-bit operands need 8, all of them working at once. Multiplication, an AND gate for every pair and an XOR tree for every column a2 b2 a2 b1 a1 b2 a2 b0 a1 b1 a0 b2 a1 b0 a0 b1 a0 b0 c4 c0 c3 c1 c2 9 AND gates and 4 XOR gates for 3-bit operands, 64 and 49 for 8-bit operands.
Figure 6. Polynomial addition over as a row of XOR gates, and polynomial multiplication as an AND array whose columns are summed by XOR trees. Neither circuit has a carry chain. Data: the gate counts are reproduced by ch33_polynomials_over_a_field.py in the companion repository.

The field multipliers of later chapters keep only a product's remainder modulo a fixed polynomial. Modulo x3+x+1x^3 + x + 1, the remainders x3 mod (x3+x+1)=x+1x^3 \bmod (x^3 + x + 1) = x + 1 and x4 mod (x3+x+1)=x2+xx^4 \bmod (x^3 + x + 1) = x^2 + x turn a product c4x4+c3x3+c2x2+c1x+c0c_4 x^4 + c_3 x^3 + c_2 x^2 + c_1 x + c_0 into (c2+c4)x2+(c1+c3+c4)x+(c0+c3)(c_2 + c_4) x^2 + (c_1 + c_3 + c_4) x + (c_0 + c_3). In matrix form the reduction is the following product over GF(2)\mathrm{GF}(2).

[r0r1r2]=[100100101100101][c0c1c2c3c4]\begin{bmatrix} r_0 \\ r_1 \\ r_2 \end{bmatrix} = \begin{bmatrix} 1 & 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 & 1 \\ 0 & 0 & 1 & 0 & 1 \end{bmatrix} \begin{bmatrix} c_0 \\ c_1 \\ c_2 \\ c_3 \\ c_4 \end{bmatrix}
(9)

So r0=c0⊕c3r_0 = c_0 \oplus c_3, r1=c1⊕c3⊕c4r_1 = c_1 \oplus c_3 \oplus c_4 and r2=c2⊕c4r_2 = c_2 \oplus c_4. Reduction respects sums, so it is a linear map over GF(2)\mathrm{GF}(2), and its matrix, in the sense of Matrices and Elimination over Finite Fields, carries the remainders of x3x^3 and x4x^4 as its last two columns. The script checks the three equations on all 32 inputs. Each 1 in those two columns is a tap, and the four taps cost four XOR gates, as Figure 7 shows.

Four XOR gates reduce the product bits c4 to c0 modulo x^3 + x + 1 to the three bits r2, r1 and r0 Reducing a product modulo x3+ x + 1 takes four XOR gates c4 to c0 are the five product bits that leave the multiplier array. c2 c4 c1 c3 c0 r2 r1 r0 c4 stands for x4, and x4 equals x2+ x, so c4 feeds r2 and r1 (taps 110) c3 stands for x3, and x3 equals x + 1, so c3 feeds r1 and r0 (taps 011) A different modulus moves the taps, so the chosen polynomial fixes the wiring.
Figure 7. Reduction of a degree-4 product modulo over . The high bits and fold back into the low three positions wherever the remainders of and have a 1. Data: the equations are reproduced by ch33_polynomials_over_a_field.py in the companion repository.

The modulus decides that wiring. Modulo x3+x2+1x^3 + x^2 + 1, the other irreducible cubic, x3x^3 leaves x2+1x^2 + 1 and x4x^4 leaves x2+x+1x^2 + x + 1, so the last two columns change and the taps move. Constructing Galois Fields chooses an irreducible polynomial for each field it builds, and that choice fixes the reduction wiring of every multiplier for the field. GF Multiplier Architectures compares the circuits that result.

Division by a fixed polynomial is a sequence of conditional XORs. In the long division of Figure 2, each step XORs in the shifted divisor when the leading bit is 1 and does nothing when it is 0, and the bits looked at form the quotient 10101. With the divisor fixed, each step is a fixed set of XOR gates enabled by one bit. The leading position always becomes 0 and is dropped, so the gates sit at the ones below the leading one, here the two low ones of 1011. Performed one bit per clock cycle, the steps become a shift register with two XOR gates, which the script runs on this division. Shift Registers and Polynomial Circuits builds this divider, and the Cyclic Codes, CRCs and Burst Errors part uses it to compute check bits.

11.Looking Ahead

The remainders modulo x3+x+1x^3 + x + 1 add and multiply among themselves, and the extended Euclidean algorithm found xx as an inverse of x2+1x^2 + 1. Ideals and Quotient Rings takes those eight remainders as a ring of their own, the way Integers and Modular Arithmetic took the remainders modulo nn, and proves that an irreducible modulus makes every nonzero remainder invertible, so that the result is a field. Constructing Galois Fields then builds the fields with 4, 8, 16 and 9 elements from irreducible polynomials like the ones found here, and Primitive Elements and Field Structure explains why some irreducible polynomials make better moduli than others. That every finite field is one of the fields built this way was proved by E. H. Moore in 1893 [4]. The algebra of this chapter is classical, and fuller treatments are in Lidl and Niederreiter [5] and McEliece [6], with the coding view in MacWilliams and Sloane [7] and Huffman and Pless [8].

12.Worked Examples

13.Exercises

References

  1. [1]Lin, Shu and Costello, Jr., Daniel J. (2004). “Error Control Coding: Fundamentals and Applications.” 2nd edition. Pearson Prentice Hall.
  2. [2]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
  3. [3]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
  4. [4]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
  5. [5]Lidl, Rudolf and Niederreiter, Harald (1996). “Finite Fields.” 2nd edition. Cambridge University Press. doi:10.1017/CBO9780511525926
  6. [6]McEliece, Robert J. (1987). “Finite Fields for Computer Scientists and Engineers.” Springer US. doi:10.1007/978-1-4613-1983-2
  7. [7]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
  8. [8]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