Understanding Cryptography by Christof Paar and Jan Pelzl - Chapter 4 Solutions - Ex4.7

• 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.7

We consider the field \(GF(2^4)\), with \(P(x) = x^4 + x + 1\) being the irreducible polynomial. Find the inverses of \(A(x) = x\) and \(B(x) = x^2 + x\). You can find the inverses either by trial and error, i.e., brute-force search, or by applying the Euclidean algorithm for polynomials. (However, the Euclidean algorithm is only sketched in this chapter.) Verify your answer by multiplying the inverses you determined by A and B, respectively.

Solution

This solution is verified as correct by the official Solutions for Odd-Numbered Questions manual.

Rather than implementing the Extended Euclidian Algorithm, I will instead just be finding them via trial and error using the code I wrote for Ex4.3. The number of possiblities to check is only 16 (\(2^4\)) for each of the two subquestions, so it’s more time-efficient to check manually:

The multiplicative inverse is therefore \(x^3 + 1\). This answer can be verified as correct (assuming my code is correct) by placing the following python code in the __main__ section of the script written for Ex4.3:

    mod = Mod2Polynomial([1, 1, 0, 0, 1])
    a = Mod2Polynomial([0, 1])
    b = Mod2Polynomial([1, 0, 0, 1])

    print a, "\t", b
    print a * b % mod

The multiplicative inverse is therefore \(x^2 + x + 1\). This answer can be verified as correct (assuming my code is correct) by placing the following python code in the __main__ section of the script written for Ex4.3:

    mod = Mod2Polynomial([1, 1, 0, 0, 1])
    a = Mod2Polynomial([0, 1, 1])
    b = Mod2Polynomial([1, 1, 1, 0])

    print a, "\t", b
    print a * b % mod

Thomas Busby

I write about computing stuff

Tweet Share