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).*

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)

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

- (a)
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)*

- (a)
For the following questions, use polynomial arithmetic over GF(2):

- (a) What is the product of
*x*and^{7}+x^{6}+1*x*?^{4}+x^{3}+x^{2} - (b) What are the quotient and remainder when
*x*is divided by^{11}+x^{8}+x^{4}+x^{3}+x^{2}*x*?^{8}+x^{4}+x^{3}+x+1 - (c) What is the product of
*x*and^{7}+x^{6}+1*x*modulo^{4}+x^{3}+x^{2}*x*?^{8}+x^{4}+x^{3}+x+1

- (a) What is the product of
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^{8})*not*need to rework the calculation -- just re-write the result using hexadecimal notation).Calculate {

`16`

}*×*{`64`

}, where these values are hexadecimal notation for elements of GF*(2*-- use the AES modulus (^{8})*x*).^{8}+x^{4}+x^{3}+x+1