Understanding Cryptography by Christof Paar and Jan Pelzl - Chapter 4 Solutions - Ex4.8
- 1 min- Return to index
- Exercise 4.1
- Exercise 4.2
- Exercise 4.3
- Exercise 4.4
- Exercise 4.5
- Exercise 4.6
- Exercise 4.7
- Exercise 4.8
- Exercise 4.9
- Exercise 4.10
- Exercise 4.11
- Exercise 4.12
- Exercise 4.13
- Exercise 4.14
- Exercise 4.15
- Exercise 4.16
Exercise 4.8
Find all irreducible polynomials
- of degree 3 over \(GF(2)\),
- of degree 4 over \(GF(2)\).
The best approach for doing this is to consider all polynomials of lower degree and check whether they are factors. Please note that we only consider monic irreducible polynomials, i.e., polynomials with the highest coefficient equal to one.
Solution
I haven’t yet verified this solution independently. If you spot any mistakes, please leave a comment in the Disqus box at the bottom of the page.
-
There are two irreducible polynomials in \(GF(2)\) of degree 3:
-
\(x^3+x+1\)
-
\(x^3+x^2+1\)
-
-
There are three irreducible polynomials in \(GF(2)\) of degree 4:
-
\(x^4+x+1\)
-
\(x^4+x^3+x^2+x+1\)
-
\(x^4+x^3+1\)
-
Thomas Busby
I write about computing stuff