4
$\begingroup$

I am new to this field. I am doing some cryptography course and have encountered $\text{GF}(2^8)$ in the famous AES algorithm. Although I do not have a strong relevant math background with this stuff(ring/field), I am really interested in it. My textbook has a question which says to prove that:

$$x^8+x^4+x^3+x+1$$ is irreducible over $\mathbb{Z}_2[x]$. I am stuck at this point where I don't have much intuition about proving irreducibility over the whole $\mathbb{Z}_2[x]$. Any help will be much appreciated!

$\endgroup$
0

1 Answer 1

8
$\begingroup$

Definition: A non-constant polynomial is said to be irreducible if it is cannot be factored into a product of two non-constant polynomials. In other words; if $p(x) = q(x)t(x)$ and it is irreducible then either $q(x)$ or $t(x)$ is a constant polynomial.

One way to prove that is $p(x) = x^8+x^4+x^3+x+1$ is irreducible over $\operatorname{GF}(2)[x]$ is checking the divisibility by the lower degree irreducible polynomials. First degree 1, then degree 2, then degree 3, and degree 4 will be enough to determine since a degree 8 can be factored into two polynomials with possible degrees as $1\cdot 7,2\cdot 6, 3\cdot 5$, and $4 \cdot 4$.

Below all the arithmetic is performed on $\operatorname{GF}(2)[x]$

  1. degree polynomials are $x$ and $x+1$. We can check the divisibility by setting $p(0) \stackrel{?}{=} 0$ or $p(1) \stackrel{?}{=} 0$. $p(0) = 1 \neq 0$ and also $p(1) = 1 \neq 0$. Therefore degree one polynomials doesn't divide $p(x)$. This is by the factor theorem and here a nice proof in Math.SE.

  2. degree polynomials, where we have four polynomials;

\begin{align} & x^2+x+1\\ & x^2+x \\ & x^2+1\\ & x^2\\ \end{align}

Let see why $x^2+1$ is not irreducible;

\begin{align} (x+1)\,(x+1)&=x\,(x+1)+1\,(x+1)&&\text{by distributivity}\\ &=x^2+1\,x+1\,x+1&&\text{.}\\ &=x^2+(1+1)\,x+1&&\text{.}\\ &=x^2+(0)\,x+1&&\text{since the coefficients are in }\operatorname{GF}(2)\\&=x^2+1 \end{align}

with a quick check that only $x^2+x+1$ is irreducible. To see that $p(x)$ is not divisible by $x^2+x+1$ perform division and look for the remainder. One can use this Sage script

R = PolynomialRing(GF(2),'x')
x = R.gen()
p = x^8+x^4+x^3+x+1
q = x^2 + x + 1
p.quo_rem(q)

the output is $(quo = x^6 + x^5 + x^3, rem = x + 1)$, . i.e cannot divide.

  1. degree irreducible polynomials

\begin{align} & x^3 + x + 1 \\ & x^3 + x^2 + 1 \end{align}

  1. degree irreducible polynomials

\begin{align} & x^4 + x + 1 \\ & x^4 + x^3 + 1\\ & x^4 + x^3 + x^2 + x + 1 \end{align}

These polynomials are generated with SageMath

degree=4
R = GF(2)['x']
for p in R.polynomials(degree):
     if p.is_irreducible():
         print(p)

To test all the division use the below

R = PolynomialRing(GF(2),'x')
x = R.gen()
p = x^8+x^4+x^3+x+1
lst = [ x^2 + x + 1,  x^3 + x + 1,  x^3 + x^2 + 1,  x^4 + x + 1 , x^4 + x^3 + 1, x^4 + x^3 + x^2 + x + 1]

for t in lst:
    print(p.quo_rem(t))

The output is

(x^6 + x^5 + x^3, x + 1)
(x^5 + x^3 + x^2 + 1, x^2)
(x^5 + x^4 + x^3, x + 1)
(x^4 + x, x^3 + x^2 + 1)
(x^4 + x^3 + x^2 + x + 1, x^3 + x^2)
(x^4 + x^3 + 1, x^3 + x^2)

Therefore $p(x) = x^8+x^4+x^3+x+1$ is irreducible over $\operatorname{GF}(2)[x]$


Note 1: low degree irreducible binary polynomials are important in Cryptography since they reduce the required arithmetic. Gadiel Seroussi, in 1998, made a huge list in Table of Low-Weight Binary Irreducible Polynomials. The list contains binary irreducible polynomials up to 10000 degrees.

Note 2: A014580 from The On-Line Encyclopedia of Integer Sequences contains a list of binary polynomials, encoded in binary, or evaluated when $x=2$. The $p(2)$ is 283.

2, 3, 7, 11, 13, 19, 25, 31, 37, 41, 47, 55, 59, 61, 67, 73, 87, 91, 97, 103, 109, 115, 117, 131, 137, 143, 145, 157, 167, 171, 185, 191, 193, 203, 211, 213, 229, 239, 241, 247, 253, 283, 285, 299, 301, 313, 319, 333, 351, 355, 357, 361, 369, 375,...

The bolds irreducibles are listed in this answer.

Note 3: A001037 keeps the number of degree-n irreducible polynomials over $\operatorname{GF}(2)$. There are 18 in degree 8 and $p(x)$ among the lowest possible weight.

degree 1  2  3  4  5  6  7   8
count  1, 2, 1, 2, 3, 6, 9, 18

and this can be counted by $$L_q(n) = \frac{1}{2} \sum_{d|n} \mu (\frac{n}{d})q^d$$

$\endgroup$
3
  • 1
    $\begingroup$ @kelalaka Thank you so much for such a detailed and great explanation! I am much grateful to you for your kind help. $\endgroup$ Mar 2, 2020 at 18:19
  • 1
    $\begingroup$ Addition: The question's $\Bbb Z_2$ is this answer's $\operatorname{GF}(2)$. The question's $\text{GF}(2^8)$ can be seen as the answer's $\operatorname{GF}(2)[x]$ restricted to polynomials with degree less than $8$, under the same addition law, and a different multiplication law: $r\cdot s$ in $\text{GF}(2^8)$ is defined to be $(r\cdot s)\bmod(x^8+x^4+x^3+x+1)$ in $\operatorname{GF}(2)[x]$. That modified multiplication is an internal law. It inherits associativity, commutativity, distributivity, neutral (the polynomial $1$). It is such that every element except $0$ has an inverse. $\endgroup$
    – fgrieu
    Mar 3, 2020 at 14:59
  • 2
    $\begingroup$ @fgrieu I used to use $\Bbb Z_2$, nowadays I prefer $\operatorname{GF}(2)$ to honor the Galois. I wonder what would have been the science if he didn't die in the duel. $\endgroup$
    – kelalaka
    Mar 3, 2020 at 16:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.