Manipulation of Binary Messages as Polynomials in GF(2)

Manipulation of long binary values requires some special techniques. The polynomials notation lends itself to computation in hardware using only shift registers and exclusive-OR (XOR) gates. Once the mathematics of polynomials has been defined, the concept of irreducible polynomials can be introduced.

Introduction to the Galois Field GF(2)

1. Single bit binary values are defined on a set {0,1} which constititutes a finite field or Galois field labeled GF(2). For this field the addition operation is defined as being modulo 2 addition: 
       0 + 0 = 0     0 + 1 = 1    1 + 0 = 1     1 + 1 = 0
Significantly, this is equivalent to the exclusive-OR operation. The set satisfies the definition of an additive group: the properties of closure, identity, inverse, and associative can be confirmed for addition in this set. The operation is also commutative. For this field the multiplication operation is defined as: 
       0 × 0 = 0     0 × 1 = 0    1 × 0 = 0     1 × 1 = 1
While this is like normal multiplication, it is also equivalent to a logical AND operation. The set satisfies the definition of a multiplicative group: the properties of closure, identity, inverse, and associative can be confirmed for multiplication in this set (excluding the zero which has no inverse). The operation is also commutative.

In summary the set {0,1} is both an additive group and multiplicative group and the operation of multiplication is distributive over addition (e.g. a × [b+c] = a×b + b×c ) both operations are commutative and the set defines a field named GF(2). This field forms the basis for larger fields of the form GF(2m).

These mathematical definitions constitute the theoretical underpinnings for all the manipulations to follow. The rules of everyday math work on real numbers because the real numbers form a field. The same familiar operations work with the Galois field GF(2) with the major difference being that modulo 2 addition is used.

2. Multi-bit binary values can be represented as polynomials with coefficents from GF(2) or the set {0,1}.

For example, the 6-bit binary sequence 110011 can be written as

1 x5 + 1 x4 + 0 x3 + 0 x2 + 1 x1 + 1 x0

and simplified as:

x5 + x4 + x + 1

or as polynomial terms in brackets as:

(110011)

or the same bits in decimal format as:

(51)

The degree of a polynomial is the power of the highest non-zero coefficient. The above example shows a polynomial of "degree 5"; note that a degree 5 polynomial spans 6 bits.

A monic polynomial is defined as having 1 as the highest order coefficient as in this example.

3. Polynomials can be manipulated using the usual arithmetic rules, in particular, the polynomial powers add under multiplication, as expected.

Example 1: The product (110011) x (10) = (1100110) can be written as:

(x5 + x4 + x + 1) (x) = x6 + x5 + x2 + x

4. Polynomials always use modulo 2 addition as described above.

Example 2: The product (11) x (11) can be computed as: 

    
              11
            x 11
            ----
              11
           + 110
            ----
             101    Note modulo 2 addition
and as a polynomial:
(x + 1) (x + 1) = x2 + x + x + 1 = x2 + 1
Note that x + x = 0 when simplifying this result.

Note that this result is not "3 x 3 = 9" as this is not ordinary binary arithmetic!

5. The rules for subtraction follow from addition (because 1+1=0, then 0-1=1) and are also equivalent to the exclusive-OR operation, as: 

       0 - 0 = 0     0 - 1 = 1    1 - 0 = 1     1 - 1 = 0

Therefore, subtraction is the same as addition in GF(2).

6. With these rules in mind, a division such as (x2 + 1) / (x + 1)  or  (101) / (11) can be accomplished: 

                  1 1     quotient = x + 1
              ________
          1 1 ) 1 0 1
                1 1
               ----
                  1 1      Note modulo 2 subtraction
                  1 1
                  ----
                    0      remainder = 0

Therefore: x2 + 1 = (x + 1)(x + 1).

The polynomial (x + 1) is a factor of x2 + 1.

An polynomial that has no factors other than 1 and itself is called an irreducible polynomial or equivalently a prime polynomial with the analogy being a prime integer.

Note again that (101) is not the integer 5 and the polynomial (101) is not prime (irreducible)!

Table of Polynomial Factors

Review of Prime Numbers

Parallels with irreducible polynomials are found with prime integers in the familiar decimal world.

The prime integers {2,3,5,7,11,13,17,19,23,29,31,37...} have no factors other than 1 and themselves.

To determine if a number such as 37 is prime, it could be tested against all possible factors from 2 to 36. In practice, only odd potential factors need to be tried once 2 is tested. In any case, testing can stop when the square root of the number is reached. Some observations can help when checking by hand:

For example, to check if 37 is prime, test only {2,3,5} (by inspection) and stop after the square root of 37.

Similarly, to check if 137 is prime, test only {2,3,5,7,9,11} . (Although 9 could be skipped after eliminating 3 as a factor.)

In summary, it is only necessary to test with prime numbers up to the square root.

It should be noted that factoring very large integers represents a formidable computational challenge for which no dramatic shortcuts exist to simplify the task.

Factoring Polynomials

Following the same logic as for integers, polynomials can readily be tested for possible factors:

Example 3:

Determine if the polynomial P(x) is irreducible, where P(x) = x6 + x5 + x2 + x = (1100110)

1. By inspection, since the smallest term is 0, then (10)=x is a factor.

2. Since there is an even (4) number of terms, then (11)=x+1 is also a factor.

By either of these tests, the polynomial P(x) is not irreducible. There is no need for further calculations.

Check: The polynomial P(x) = (1100110) has factors P(x) = (10)(11)(11)(11)(11)(11)

Example 4:

Completely factor the polynomial P(x) = x5 + x4 + x3 + x2 + x + 1 = (111111).

1. By inspection, since the smallest term is 1, then (10)=x is not a factor.

2. By inspection, since there is an even (6) number of terms, then (11)=x+1 is a factor.

Check with a test division. As expected, division by (x+1) yields a zero remainder, and a factor is found. This polynomial is not irreducible. 

      10101  quotient = x4 + x2 + 1
   --------
11 ) 111111
     11      
     --
      011
       11
       --
        011
         11
         --
         00   remainder = 0
Therefore: x5 + x4 + x3 + x2 + x + 1 = (x+1) (x4+x2+1)

It is now necessary to check for further factors of the quotient q(x) = x4+x2+1 = (10101).

1. By inspection, since the smallest term is 1, then (10)=x is not a factor.

2. By inspection, since there is an odd (3) number of terms, then (11)=x+1 is not factor.

3. The highest term is x4, terms up to x2 must be tested (corresponding to the square root).

Consequently, it is necessary to test, at most, the following 'odd' polynomials: 

       a.   (11) : x + 1   = (done by inspection)  
       b.  (101) : x2 + 1  = (x+1)(x+1)
       c.  (111) : x2 + x + 1

And the only remaining test is with x2 + x + 1 = (111): 

        111   quotient  = x2 + x + 1
    -------
111 ) 10101
      111
      ---
       100
       111
       ---
        111
        111
        ---
        000   remainder = 0

The division (1011111) / (111) = (111) with remainder 0

Therefore, the polynomial P(x) = (111111) has factors P(x) = (11) (111) (111).

Example 5:

Completely factor the polynomial P(x) = x6 + x5 + 1 = (1100001).

1. By inspection, since the smallest term is 1, then (10)=x is not a factor.

2. By inspection, since there is an odd (3) number of terms, then (11)=x+1 is not a factor.

3. The highest term is x6, terms up to x3 must be tested (corresponding to the square root).

It is necessary to test, at most, the following 'odd' polynomials: 

       a.   (11) : x + 1            = (done by inspection)  
       b.  (101) : x2 + 1           = (x+1)(x+1)
       c.  (111) : x2 + x + 1
       d. (1001) : x3 + 1           = (x+1)(x2+x+1)
       e. (1011) : x3 + x + 1
       f. (1101) : x3 + x2 + 1
       g. (1111) : x3 + x2 + x + 1  = (x+1)(x2+1)

Where some test divisions could be avoided if the obvious factorable terms are skipped, as shown above.
Test division by (111): 
        10110
    ---------
111 ) 1100001
      111
      ---
       0100
        111
        ---
         110
         111
         ---
          011  = remainder
Test division by (1011): 
          1110
     ---------
1011 ) 1100001
       1011
       ----
        1110
        1011
        ----
         101
         1011
         ----
          0011  = remainder
Test division by (1101): 
         1001
     ---------
1101 ) 1100001
       1101
       ----
        001001
          1101
          ----
          0100   = remainder

Because all possible factors of P(x) have been tested up to the square root of P(x), then P(x) is irreducible.

Note that only three long divisions were actually required to check this polynomial of degree 6.

Online Factoring Tool

Table of Irreducible Polynomials

Primitive Polynomials

Certain irreducible polynomials are distinguished by being primitive. The properties of these special irreducible polynomials are especially important in digital communications.

Definition: An irreducible polynomial P(x) of degree N is primitive if P(x) is a factor of xM+1 for M=2N-1 and no smaller M.

In GF(2), the expression xM+1 is equivalent to xM-1 and this definition may be written using either form.

Example 6:
A Primitive Polynomial - The polynomial P(x)=x3+x+1=(1011) of degree 3 is irreducible. Let M=23-1=7. Because P(x) is a factor of x7+1=(10000001) but is not a factor of any smaller xM+1, then P(x) is primitive.

Example 7:
A Prime but not Primitive Polynomial - The polynomial P(x)=x4+x3+x2+x+1=(11111) of degree 4 is irreducible. Let M=24-1=15. Although P(x) is a factor of x15+1=(1000000000000001) it is also factor of the smaller x5+1=(100001) and P(x) is not primitive.

Table of Factors of xN+1

Polynomial Division in Hardware

The application of polynomials to the manipulation of binary numbers has a practical significance in the way in which the operations are actually performed in a digital circuit. Normally, it would be painstaking and slow to perform long division on large integers. The above example could be performed in hardware with simple XOR-gates and shift registers.

Observe the value 11 (highlighted) as the division proceeds below. This value is essentially being shifted across P(x). It has already been noted that subtraction is equivalent to XOR. Consequently, the division reduces to shifting 11 across P(x) and performing the XOR operation if the msb of both values equals 1. 

              1 0 1 1 1 1 1  = x6 + x 4 + x3 + x2 + x + 1
          -----------------
      1 1 ) 1 1 1 0 0 0 0 1
            1 1               XOR        
              ---
              0 1  
              1 1             no!
              ---
              0 1 0
                1 1           XOR
              -----
                  1 0
                  1 1         XOR
                  ---
                    1 0
                    1 1       XOR
                    ---
                      1 0
                      1 1     XOR
                      ---
                        1 1
                        1 1   XOR
                        ---
                          0       remainder = 0