A printable PDF is available.

Assignment 2 - Due Wednesday, February 12

This assignment is more straightforward than usual, covers only one chapter, and you only have one week. It will count only half as much as your normal assignments (it will be graded out of 50 points).

1. Compute the following GCD's using the Euclidean algorithm presented in Section 4.2. Show each step and intermediate result.

   • (a) gcd(21703, 44850)
   • (b) gcd(215258, 71512)

2. Compute gcd(612, 4931) using the Extended Euclidean algorithm given in Section 4.3. Show each step and intermediate result. Note that for inputs a and b, the Extended Euclidean algorithm finds not only gcd(a,b) but also values x and y so that ax+by=gcd(a,b) -- make sure you clearly mark x and y in your final answer.

3. Prove that for any positive values a, b, c, and n,

   • (a) (a×b) mod n = [(a mod n)×(b mod n)] mod n
   • (b) (a×b×c) mod n = [(a×b) mod n]×c mod n

4. For each of the following equations, find an integer x that satisfies the equation.

   • (a) 3x == 4 ( mod 5)
   • (b) 3x == 4 ( mod 7)
   • (c) 9x == 1 ( mod 11)

5. For the following questions, use polynomial arithmetic over GF(2):

   • (a) What is the product of x⁷+x⁶+1 and x⁴+x³+x²?
   • (b) What are the quotient and remainder when x¹¹+x⁸+x⁴+x³+x² is divided by x⁸+x⁴+x³+x+1?
   • (c) What is the product of x⁷+x⁶+1 and x⁴+x³+x² modulo x⁸+x⁴+x³+x+1?

6. Part (c) in the previous question can be viewed as a field operation over GF(2⁸) -- rewrite that operation and product using the hexadecimal notation described in Section 4.7 (you do not need to rework the calculation -- just re-write the result using hexadecimal notation).

7. Calculate {16}×{64}, where these values are hexadecimal notation for elements of GF(2⁸) -- use the AES modulus (x⁸+x⁴+x³+x+1).