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 pm elements for some prime p, and Integers and Modular Arithmetic built the field 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+1 and 0111 as x2+x+1, and 110001 is their product x5+x4+1 with coefficients in GF(2). Lin and Costello compute with exactly these bit-string polynomials [1].
The chapter adds, multiplies and divides such polynomials over GF(2), GF(3) and 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) 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.
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⋅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=49, the XOR of the shifted copies. Figure 1 sets the two sums side by side.
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 k of a string as the coefficient of xk. Multiplying x3+x+1 by x2+x+1 term by term gives one product xi⋅xj=xi+j for each pair of terms, so the coefficient of xk counts the pairs with i+j=k, which is exactly the count in column k. With coefficients in GF(2), where 1+1=0, only the parity of that count survives, and the product is x5+x4+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.
Over GF(2), adding x3+x+1 and x2+x+1 adds the coefficients of like powers. The terms x and 1 appear in both and cancel, because 1+1=0, so the sum is x3+x2, or 1011⊕0111=1100 as bit strings. Larger fields follow the same rule. Over GF(3), (2x2+x+1)+(x+2)=2x2+2x, since 3≡0, and over GF(5), (3x2+4x+2)+(2x+3)=3x2+x.
Multiplication pairs every term of one factor with every term of the other. Over GF(3), the product of 2x2+x+1 and x+2 collects 2⋅1=2 in x3, 2⋅2+1⋅1=5 in x2, 1⋅2+1⋅1=3 in x, and 1⋅2=2 in the constant. Reducing 2, 5, 3 and 2 modulo 3 gives 2x3+2x2+2. Over GF(5), the product of 3x2+4x+2 and 2x+3 has the sums 3⋅2=6, 3⋅3+4⋅2=17, 4⋅3+2⋅2=16 and 2⋅3=6, which reduce modulo 5 to x3+2x2+x+1.
The zero polynomial has no degree, so this chapter writes "r=0 or degr<degg" wherever zero can occur. The letter x only keeps the positions apart, a point the next section makes precise.
Here ai and bj are the coefficients of f and g, and every sum is taken in F. The product rule is a convolution, the sliding sum of products that a digital filter computes, and over GF(2) each aibj is an AND and each sum an XOR. Rings and Fields met F[x] as a ring. The script confirms the ring axioms of GF(2), GF(3), GF(5), Z4 and Z8 on all triples of elements, 8, 27, 125, 64 and 512 of them.
The polynomials of degree below n also form a vector space of dimension n over F, in the sense of Vector Spaces over Finite Fields, with the basis 1,x,…,xn−1, so over GF(q) there are qn 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 f and g in F[x] the law reads as follows.
deg(fg)=degf+degg
(2)
If f has degree m and g has degree n, the top term of fg comes from one product only, ambnxm+n, and ambn=0 because a field has no zero divisors. The script checks the law on all 676 pairs of nonzero polynomials over GF(3) of degree below 3.
Evaluating a polynomial puts an element a of F in place of x and computes in F. Over GF(2), f(x)=x2+x gives 0+0=0 at 0 and 1+1=0 at 1. So f, a nonzero polynomial with the coefficient bits 110, defines the same function as the zero polynomial.
Proof. The coefficient of x2 in x2+x is 1, so the polynomial is not zero, and the computation above gives 0 at both elements. For GF(p), the coefficient of xp in xp−x is 1, while Corollary: Fermat for every integer, in Integers and Modular Arithmetic, gives ap≡a(modp) for every integer a. So ap−a=0 for every element of GF(p). ■
The script finds x3−x zero at all three elements of GF(3) and x5−x zero at all five of GF(5). A count forces this. There are only 22=4 functions from GF(2) to itself, but 16 polynomials of degree below 4, and exactly four of them vanish at both points, namely 0, x2+x, x3+x and x3+x2, each a multiple of x2+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.
Integers and Modular Arithmetic divided an integer a by a positive n to get a=qn+r with 0≤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), divide x7+x4+x+1, the bit string 10010011, by x3+x+1, the bit string 1011.
The leading term x7 is x4 times x3, so the first quotient term is x4, and subtracting x4(x3+x+1) XORs in 1011 shifted four places. That gives 10010011⊕10110000=100011, the polynomial x5+x+1. Its leading term gives the quotient term x2, and 100011⊕101100=1111. The quotient term 1 then gives 1111⊕1011=100, which is x2, of degree below 3, so the division stops.
The quotient is x4+x2+1, the string 10101, and the remainder is x2. Multiplying back, (x4+x2+1)(x3+x+1)=x7+x4+x2+x+1, and adding the remainder x2 restores the dividend. Figure 2 lays the steps out as integer long division, with every subtraction an XOR.
Figure 2. Long division of x7+x4+x+1 by x3+x+1 over GF(2). 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=degg, and let bm be the leading coefficient of g. Existence goes by induction on the degree of f. If f=0 or degf<m, take q=0 and r=f. Otherwise let n=degf≥m, with leading coefficient an, and assume the claim for every polynomial of degree below n. The polynomial anbm−1xn−mg has degree n and leading coefficient anbm−1bm=an, so in f1=f−anbm−1xn−mg the terms in xn cancel, and f1=0 or degf1<n. By the induction hypothesis f1=q1g+r with r=0 or degr<m, and then f=(q1+anbm−1xn−m)g+r. For uniqueness, suppose f=qg+r=q′g+r′ with both remainders satisfying the degree condition. Then (q−q′)g=r′−r. If q=q′, the left side has degree at least m by Equation 2, while the right side is 0 or has degree below m, which is impossible. So q=q′, and then r=r′. ■
The proof uses the field twice. Existence needs the inverse bm−1, and uniqueness needs deg((q−q′)g)≥m, which holds whenever bm 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) the inverse is real work. Divide 3x3+x2+4x+2 by 2x2+3x+1. The inverse of the leading coefficient 2 is 3, since 2⋅3=6≡1, so the first quotient term is 3⋅3x=4x, and subtracting 4x(2x2+3x+1)=3x3+2x2+4x leaves 4x2+2. The next quotient term is 4⋅3=12≡2, and subtracting 2(2x2+3x+1)=4x2+x+2 leaves 4x. Table 1 records the two steps.
Table 1. Dividing 3x3+x2+4x+2 by 2x2+3x+1 over GF(5), where each quotient term multiplies by the inverse 3 of the leading coefficient 2
Step
Leading term left
Quotient term
Subtracted
Left over
first
3x3
3⋅3x=4x
3x3+2x2+4x
4x2+2
second
4x2
4⋅3=2
4x2+x+2
4x
Source: reproduced by ch33_polynomials_over_a_field.py.
The quotient is 4x+2 and the remainder is 4x. Indeed (4x+2)(2x2+3x+1)=8x3+16x2+10x+2=3x3+x2+2 over GF(5), and adding 4x restores the dividend. The script confirms existence and uniqueness on all 960 pairs over GF(2) with f of degree below 6 and g nonzero of degree below 4.
A remainder modulo a fixed polynomial behaves like a remainder modulo a fixed integer. Modulo g=x3+x+1 over GF(2), x3=g+x+1 leaves x+1, so x4 leaves x2+x and x3+x2 leaves x2+x+1. Their product x7+x6 leaves x2, and so does the product of their remainders, (x2+x)(x2+x+1)=x4+x. Their sum x4+x3+x2 leaves 1, and so does (x2+x)+(x2+x+1).
Proof. Write f=q1g+r1 and h=q2g+r2. Then f+h=(q1+q2)g+(r1+r2), and r1+r2 is 0 or has degree below degg, so by uniqueness it is the remainder of f+h. For the product, fh=(q1q2g+q1r2+q2r1)g+r1r2. Dividing r1r2=q3g+r3 gives fh=(q1q2g+q1r2+q2r1+q3)g+r3, so by uniqueness fh and r1r2 share the remainder r3. ■
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+1 on all 1,024 pairs of polynomials of degree below 5. In the language of Groups and Cosets, the multiples of g form a subgroup of F[x] under addition, and each remainder names one of its cosets. Modulo x3+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.
Over GF(2), the polynomials x5+x4+1 and x4+x2+1 share a factor. The first is (x2+x+1)(x3+x+1), and the second is (x2+x+1)2, since Corollary: Squaring spreads the bits, in Rings and Fields, squares x2+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∣g and g∣f, then g=uf and f=vg, so f(1−vu)=0. Since F[x] has no zero divisors, vu=1, and by Corollary: The units of a polynomial ring, u and v are nonzero constants. A nonzero f with leading coefficient a has exactly one monic associate, a−1f, 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 g and r divides qg+r=f. A polynomial that divides f and g divides f−qg=r. ■
Proof. Each ri+1 is 0 or has degree below degri, so the nonzero remainders after r1 have strictly falling degrees between 0 and degg−1. There are at most degg of them, and the division after the last produces 0. Let rk be the last nonzero remainder. By the lemma, applied to each division in turn, the common divisors of f and g are those of r1 and r2, then of r2 and r3, and finally of rk and 0, which are the divisors of rk. So rk is a common divisor that every common divisor divides. ■
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+1 by x4+x2+1 gives the quotient x+1 and the remainder x3+x2+x. Dividing x4+x2+1 by x3+x2+x gives the quotient x+1 and the remainder x2+x+1, which divides x3+x2+x exactly x times. The degrees run 5, 4, 3 and 2 before the remainder vanishes, and the greatest common divisor is x2+x+1. The script runs the algorithm on all 961 pairs of nonzero polynomials over GF(2) of degree below 5 and confirms each answer against every common divisor.
The integer algorithm carried cofactors si and ti with ri=sia+tib in every row, and the same columns work for polynomials. Row 0 holds r0=f with (s0,t0)=(1,0), row 1 holds r1=g with (s1,t1)=(0,1), and each later row follows from the quotient qi of ri−1 by ri.
gcd(f,g)=sf+tg
(5)
Proof. If g=0 and a is the leading coefficient of f, then gcd(f,g)=a−1f, so s=a−1 and t=0. Otherwise run the extended algorithm. Rows 0 and 1 satisfy ri=sif+tig by their choice, and if rows i−1 and i satisfy it, then Equation 4 gives ri+1=(si−1f+ti−1g)−qi(sif+tig)=si+1f+ti+1g. So every row does. The last nonzero remainder rk is a greatest common divisor, and if c is its leading coefficient, then gcd(f,g)=(c−1sk)f+(c−1tk)g. ■
Figure 3 runs the table on f=x5+x4+1 and g=x4+x2+1 over GF(2), where subtraction is addition. Row 2 takes s2=1 and t2=0−(x+1)⋅1=x+1, and row 3 takes s3=0−(x+1)⋅1=x+1 and t3=1−(x+1)2=x2. 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
(6)
The first product is x6+x4+x+1, the second is x6+x4+x2, and their sum over GF(2) is x2+x+1.
Figure 3. The extended Euclidean algorithm for x5+x4+1 and x4+x2+1 over GF(2). Each row is ri=sif+tig, and the boxed row gives gcd(f,g)=x2+x+1 with its cofactors. Data: computed by ch33_charts.py in the companion repository.
Over GF(3) the subtractions carry signs and the leading coefficients need inverses. Take f=x3+x2+x+1=(x+1)(x2+1) and g=2x2+1=(x+1)(2x+1), though the algorithm does not need the factorizations. The inverse of 2 is 2 itself, since 2⋅2=4≡1. Dividing f by g gives the quotient 2x+2 and the remainder 2x+2, and dividing g by 2x+2 gives the quotient x+2 and the remainder 0. Table 2 carries the cofactors.
Table 2. The extended Euclidean algorithm for x3+x2+x+1 and 2x2+1 over GF(3)
i
ri
qi
si
ti
0
x3+x2+x+1
1
0
1
2x2+1
2x+2
0
1
2
2x+2
x+2
1
x+1
3
0
2x+1
2x2+2
Source: reproduced by ch33_polynomials_over_a_field.py.
Row 2 says f+(x+1)g=2x+2, and indeed (x+1)(2x2+1)=2x3+2x2+x+1, which added to f gives 3x3+3x2+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+1, and gcd(f,g)=x+1.
Bezout's identity also computes inverses. Over GF(2), look for b with (x2+1)bmod(x3+x+1)=1 by running the table on f=x3+x+1 and g=x2+1. The first division, x3+x+1=x(x2+1)+1, already leaves 1, as Table 3 shows.
Table 3. The extended Euclidean algorithm for x3+x+1 and x2+1 over GF(2), which finds the inverse of x2+1
i
ri
qi
si
ti
0
x3+x+1
1
0
1
x2+1
x
0
1
2
1
x2+1
1
x
3
0
x2+1
x3+x+1
Source: reproduced by ch33_polynomials_over_a_field.py.
Row 2 reads 1=1⋅(x3+x+1)+x(x2+1), and taking remainders modulo x3+x+1 removes the first term. So the inverse of x2+1 is x, and directly x(x2+1)=x3+x=(x3+x+1)+1. In general, when gcd(f,g)=1 the last nonzero remainder is a nonzero constant c, and c−1 times its t entry is the inverse of g modulo f, the scaling the proof of Bezout's identity uses. Over GF(2) the constant is 1. Over GF(3), the table for f=x2+1 and g=x+1 stops at r2=2 with t2=2x+1, so the inverse of x+1 is 2(2x+1)=x+2, and indeed (x+1)(x+2)=x2+2=(x2+1)+1. Why every nonzero remainder modulo an irreducible polynomial has such an inverse is explained in Ideals and Quotient Rings.
Over GF(5), the polynomial f(x)=x3+2x+1 takes the value 8+4+1=13≡3 at 2. Dividing f by x−2, which over GF(5) is x+3, gives the quotient x2+2x+1 and the remainder 3, the same number.
f(x)=q(x)(x−a)+f(a)
(7)
Proof. The divisor x−a has degree 1, so the division algorithm gives f=q⋅(x−a)+r with r a constant. Substituting a for x respects sums and products, because F is commutative, so it is a ring homomorphism from F[x] to F in the sense of Rings and Fields. Hence f(a)=q(a)(a−a)+r=r. ■
Proof. If f(a)=0, then Equation 7 reads f=q⋅(x−a). If f=h⋅(x−a), then the remainder of f by x−a is 0, and by the theorem it equals f(a). ■
The script checks the remainder theorem on all 625 polynomials over GF(5) of degree below 4, at all five points. Since each root contributes a factor, roots cannot outnumber the degree.
Proof. Induction on n. A polynomial of degree 0 is a nonzero constant and has no roots. Let n≥1, and suppose f has a root a, since otherwise there is nothing to prove. Then f=(x−a)q by the factor theorem, with degq=n−1 by Equation 2. If b=a is another root, then 0=f(b)=(b−a)q(b), and since b−a=0 and a field has no zero divisors, q(b)=0. So every other root is one of the at most n−1 roots of q, and f has at most n. ■
The bound can be met. Over GF(5), x4−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). 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 k, and it has at least k roots, so by the theorem it is zero. ■
This is the condition the section on functions promised. A polynomial over GF(q) of degree below q is fixed by its function, while x2+x over 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), both possible roots can be read straight off the bits.
Proof. Substituting 0 kills every term with a positive power of x, so f(0) is the constant term. Substituting 1 turns every term xk into 1, so f(1) is the number of nonzero terms reduced modulo 2. ■
By the factor theorem, x divides a polynomial over GF(2) exactly when its last bit is 0, and x+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)=0, which are the multiples of x+1 among them, such as x3+x2+x+1=(x+1)3 with weight 4. In hardware, f(1) is the XOR of all the bits, the parity tree of every checker in Linear Block Codes, and f(0) is a single wire.
Over GF(2), the polynomial x2+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−a would make a a root, so x2+x+1 cannot be factored at all. Polynomials like it play the part of the primes.
The only divisors of an irreducible f are the nonzero constants and the associates of f, and every polynomial of degree 1 is irreducible. The field matters. Over GF(3), x2+1 takes the values 1, 2 and 2 at 0, 1 and 2, so it is irreducible there, while over GF(2) it is (x+1)2.
Proof. If f has a root a, then f=(x−a)q with degq=degf−1≥1, so f is reducible. Conversely, if f=gh with both degrees at least 1, the degrees add to 2 or 3, so one factor has degree 1, say g=cx+d with c=0. Then a=−dc−1 gives f(a)=g(a)h(a)=0. ■
The script confirms the test for every monic polynomial of degree 2 and 3 over GF(2), GF(3) and 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 f of degree d is gh with both degrees at least 1, so the smaller factor has degree at most ⌊d/2⌋, and a divisor of it of least positive degree is irreducible. So f is irreducible exactly when no irreducible polynomial of degree at most ⌊d/2⌋ divides it.
These tests, with the rules for the roots 0 and 1, find every irreducible polynomial over 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 x and x+1 are irreducible. In degree 2 only 111, which is x2+x+1, survives. In degree 3, 1011 and 1101 survive, the polynomials x3+x+1 and x3+x2+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, 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+1 times a rootless cubic, giving (x2+x+1)(x3+x+1)=x5+x4+1 and (x2+x+1)(x3+x2+1)=x5+x+1. Six remain. Table 4 collects the results.
Table 4. Every irreducible polynomial over GF(2) of degree 1 to 5, written as bit strings with the leading coefficient on the left
Degree
Count
Irreducible polynomials
1
2
10, 11
2
1
111
3
2
1011, 1101
4
3
10011, 11001, 11111
5
6
100101, 101001, 101111, 110111, 111011, 111101
Source: reproduced by ch33_polynomials_over_a_field.py.
So 10011 is x4+x+1, 11001 is x4+x3+1, and 100101 is x5+x2+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 D, 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⌋ are needed. Over 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 b 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 x, four more to x+1, one to x2+x+1, and three survive. In degree 5 the numbers are 16, 8, 2 and 6.
Figure 4. The sieve over GF(2) up to degree 5. Multiples of x end in 0, multiples of x+1 have an even number of ones, and only x4+x2+1, x5+x4+1 and x5+x+1 need the factor x2+x+1 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 2m polynomials of each degree m, beside the curve 2m/m, which they track closely. At degree 10, 99 of the 1,024 polynomials are irreducible, and 10⋅99/1024=0.967, so close to one polynomial in m of degree m is irreducible. Irreducible Polynomials and Root Finding counts them exactly and gives tests far faster than trial division.
Figure 5. The number I(m) of irreducible polynomials over GF(2) of degree m, against all 2m polynomials of that degree and the curve 2m/m. Data: computed by ch33_charts.py in the companion repository.
The same search works over GF(3). A monic quadratic x2+bx+c has 9 choices of b and c, and by the root test it is reducible exactly when it is (x−a)(x−a′) with a≤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+1, x2+x+2 and x2+2x+2. For instance x2+x+2 takes the values 2, 1 and 2 at 0, 1 and 2.
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), for instance, x5+x4+1=(x2+x+1)(x3+x+1) has no other factorization into irreducibles.
Proof. Suppose p does not divide a. The monic gcd(p,a) divides p, so it is 1 or the monic associate of p, and the second would make p divide a. So gcd(p,a)=1, and Bezout's identity gives 1=sp+ta. Multiplying by b gives b=spb+t(ab), and p divides both terms on the right, so p∣b. ■
The script checks the lemma for the five irreducibles of degree at most 3 over GF(2) against every pair of nonzero a and b of degree below 4, 1,125 triples in all. Irreducibility is essential, since x2+1=(x+1)2 divides (x+1)(x+1) but neither factor.
f=cp1p2⋯pk
(8)
Proof. Existence goes by induction on degf. If f is irreducible, then f=c⋅(c−1f) with c−1f monic and irreducible. Otherwise f=gh with both of lower degree, the hypothesis factors each, and comparing leading coefficients shows the constant in front is c. For uniqueness, suppose cp1⋯pk=cp1′⋯pl′. Then p1 divides p1′⋯pl′, so by the lemma, applied repeatedly, it divides some pj′. Since pj′ is irreducible and degp1≥1, the two are associates, and both are monic, so p1=pj′. Cancelling it, which is allowed because F[x] has no zero divisors, leaves two factorizations of a polynomial of lower degree. If one side is now the constant c, comparing degrees shows that the other has no factors left either. Otherwise both agree by induction. ■
Over GF(2) every nonzero polynomial is monic, so c=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=126 polynomials of degree 1 to 6 exactly once.
For example, x4+1=(x+1)4 by the freshman's dream, and x5+1=(x+1)(x4+x3+x2+x+1), since every middle term of the product appears twice and cancels. The quartic is 11111, irreducible by the table. Polynomials xn+1 factor in patterns that Minimal Polynomials and Cyclotomic Cosets explains in general.
Every operation of this chapter over GF(2) is a small circuit. Adding two polynomials of degree below m takes m XOR gates side by side, with no wire between neighbors. Multiplying them forms the m2 partial products aibj with AND gates and sums each column with XOR gates. Column k holds the products with i+j=k, so for m=3 the five columns hold 1, 2, 3, 2 and 1 products. A column of n terms needs n−1 XOR gates, so the 2m−1 columns need m2−(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.
Figure 6. Polynomial addition over GF(2) 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+1, the remainders x3mod(x3+x+1)=x+1 and x4mod(x3+x+1)=x2+x turn a product c4x4+c3x3+c2x2+c1x+c0 into (c2+c4)x2+(c1+c3+c4)x+(c0+c3). In matrix form the reduction is the following product over GF(2).
So r0=c0⊕c3, r1=c1⊕c3⊕c4 and r2=c2⊕c4. Reduction respects sums, so it is a linear map over GF(2), and its matrix, in the sense of Matrices and Elimination over Finite Fields, carries the remainders of x3 and x4 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.
Figure 7. Reduction of a degree-4 product modulo x3+x+1 over GF(2). The high bits c3 and c4 fold back into the low three positions wherever the remainders of x3 and x4 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+1, the other irreducible cubic, x3 leaves x2+1 and x4 leaves x2+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.
The remainders modulo x3+x+1 add and multiply among themselves, and the extended Euclidean algorithm found x as an inverse of x2+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 n, 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].
[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]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]Lidl, Rudolf and Niederreiter, Harald (1996). “Finite Fields.” 2nd edition. Cambridge University Press. doi:10.1017/CBO9780511525926
[6]McEliece, Robert J. (1987). “Finite Fields for Computer Scientists and Engineers.” Springer US. doi:10.1007/978-1-4613-1983-2
[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]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.