Exercise 2.3Z: Polynomial Division

• Return to book

Multiplication and division of polynomials in  $\rm GF(2)$
Note.   remainder  $r(x)$

In this exercise we deal with the multiplication and especially the division of polynomials in the Galois field  $\rm GF(2)$.  In the graph the procedure is indicated by a simple and  (hopefully)  self-explanatory example:

• Multiplying the two polynomials   $x^2 + 1$   and   $x +1$   yields the result   $a(x) = x^3 + x^2 + x + 1$.

• Dividing the polynomial   $b(x) = x^3$   by   $p(x) = x + 1$   gives the quotient   $q(x) = x^2 + x$   and the remainder   $r(x) = x$.

• One can check the latter result as follows:

$$b(x) \hspace{-0.15cm} \ = \ \hspace{-0.15cm} p(x) \cdot q(x) + r(x)\hspace{0.05cm}= \big[(x+1) \cdot (x^2+x)\big] +x =\big[x^3+ x^2+x^2+ x\big] +x = x^3\hspace{0.05cm}.$$

Hint:  This exercise belongs to the chapter  "Extension field".

Questions

1

What is the result  $a(x) = (x^3 + x + 1) \cdot (x^2 + 1)$?

	$a(x) = x^5 + x^3 + x^2 + 1$,
	$a(x) = x^5 + x^2 + x + 1$.
	$a(x) = x^6 + x^3 + x^2 + 1$-

2

Which of the polynomial divisions do not yield a remainder  $r(x) \ne 0$?

	$(x^5 + x^2 + x + 1)/(x^3 + x + 1)$.
	$(x^5 + x^2 + x + 1)/(x^2 + 1)$,
	$(x^5 + x^2 + x + 1)/(x^2)$,
	$(x^5 + x^2 + x)/(x^2 + 1)$.

3

It is   $a(x) = x^6 + x^5 + 1$   and   $p(x) = x^3 + x^2 + 1$.
Determine  $q(x)$  and  $r(x)$  according to the description equation   $a(x) = p(x) \cdot q(x) + r(x)$.

	$q(x) = x^3 + x^2 + 1, \hspace{0.2cm} r(x) = 0$,
	$q(x) = x^3 + 1, \hspace{0.2cm} r(x) = 0$,
	$q(x) = x^3 + 1, \hspace{0.2cm} r(x) = x^2$.

Solution

Solution

(1)  The modulo-2 multiplication of the two polynomials leads to the result

$$a(x) \hspace{-0.15cm} \ = \ \hspace{-0.15cm} (x^3+ x+1) \cdot (x^2+1)= x^5+x^3+ x^2+ x^3+x+1 = x^5+ x^2+x+1\hspace{0.05cm}.$$

• Thus the  proposed solution 2  is correct.

• The last solution suggestion cannot be valid already alone,  since the degree of the product polynomial would be unequal  $5$.

Example 1  for polynomial division

(2)  With the abbreviations

$$a(x) = x^5+ x^2+x+1\hspace{0.05cm},\hspace{0.4cm}p(x) = x^3+ x+1\hspace{0.05cm},\hspace{0.4cm}q(x) = x^2+ 1$$

and the result from subtask  (1)  we get  $a(x) = p(x) \cdot q(x)$.

That is:   The divisions  $a(x)/p(x)$  and  $a(x)/q(x)$  are free of remainders   ⇒   Correct are the  solutions 1 and 2.

Even without calculation one recognizes that  $a(x)/x^2$  must result in a remainder.  After calculation it results explicitly:

$$(x^5 + x^2+x+1)/(x^2) = x^3 + 1 \hspace{0.05cm},\hspace{0.4cm}{\rm remainder}\hspace{0.15cm} r(x) = x+1\hspace{0.05cm}.$$

To the last proposed solution:  We use for shortcut  $b(x) = x^5 + x^2 + x = a(x) + 1$.  This is the given quotient:

$$b(x)/q(x) = a(x)/q(x) + 1/q(x) \hspace{0.05cm}.$$

Example 2  for polynomial division

• The first quotient  $a(x)/q(x)$  gives exactly  $p(x)$  without remainder,  the second quotient  $0$,  remainder  $1$.

• Thus the remainder of the quotient  $b(x)/q(x)$  is equal to $r(x) = 1$,  as the calculation in Example 1 shows.

(3)  The polynomial division is explained in detail in Example 2.  Correct is the  proposed solution 3.