## Spring 2005 MATH 445 Homework

1st assignment (Due date: Monday, 1/24/2005): Do exercises 2.1, 2.4, 2.5,2.6,2.7,2.8,2.16 (not 2.18 as originally announced) and computer problems 2.2, 2.3, and 2.9.

2nd assignment (Due date: Monday, 1/31/2005): Read Sections 2.3, 2.4, and 2.5 of the book. Do exercises 2.9, 2.10, 2.11, 2.12 and computer problem 2.10.

Decrypt the following encrypted messages:

3rd assignment (Due date: Monday, 2/7/2005): Read Sections 2.6, 2.7, 2.8, 2.9, 2.10, and 2.11.

Do exercises 2.13, 2.14, and computer problems 2.11 and 2.12.

Extra credit problem: Implement the Berlekamp-Massey algorithm and compare it to the method from section 2.11 for finding the coefficients of the recursion satisfied by the sequence.

4th assignment: (Due date: Monday, 2/14/2005): Read Sections 3.1 to 3.4.

Do exercises 3.1 (find 2 solutions x,y instead of just one), 3.3, 3.4, 3.6, 3.13, and 3.14 and computer problems 3.1, 3.2, 3.4, 3.5, and 3.6.

5th assignment: (Due date: Monday, 2/21/2005): Read Sections 3.5 to 3.8.

Do exercises 3.7, 3.8, 3.12, 3.15 and computer problems 3.9, 3.10.

6th assignment: (Due date: Wednesday, 3/2/2005): Read Sections 3.9 to 3.10.

1. Find the order of all the elements of the group U(Z_15) and determine whether U(Z_15) is cyclic.

2. Show that in a cyclic group of size n, there are Phi(n) elements of order n. Here, Phi denotes the Euler totient function as defined in class.

Hint: Write down what it means for the group to be cyclic. This gives you a nice description of the elements of the group.

Do exercises 3.18, 3.19, and computer problems 3.11 3.12, 3.13.

7th assignment: (Due date: Friday, 3/11/2005): Review Chapter 3 and do the following problems.

1. Construct a field with 8 elements and determine both the addition and the multiplication table for this field.

2. Let GF(4) be the field with four elements as introduced in class and let GF(4)[X] be the polynomial ring with coefficients in GF(4).

a) Give a list of all polynomials in GF(4)[X] of degree at most 1.

b) The polynomial f=X^2+X+1 is a polynomial in GF(4)[X] of degree 2. Is f an irreducible GF(4) polynomial? Justify.

3. Let F be a field and let F[X] be the polynomial ring with coefficients in F. Show the polynomial X-a, where a is an element in F, is a factor of a polynomial p in F[X], exactly when p(a) is zero. Hint: use division and remainder.

8th assignment: (Due date: Friday, 3/25/2005): Read section 6.1, 6.2, 6.3.

Do exercises 6.1, 6.2, 6.4,6.5,6.6,6.7, and computer problem 6.13.

9th assignment: (Due date: Friday, 4/8/2005): Read section 6.4, 6.5, 6.7.

Do exercises 6.9, 6.10, 6.13, 6.15, and computer problems 6.2, 6.7, 6.8.

Extra credit problem: Use the quadratic sieve method to factor \$1042387\$. As a factor basis use the primes \$2,3,11,17,19,23,43,47\$. Explain all the steps of your solution.

10th assignment: (Due date: Friday, 4/15/2005): Read section 7.1, 7.2, 7.3, 7.4.

Do exercises 7.2, 7.3, 7.4, and computer problems 7.1, 7.2,7.4.

11th assignment: (Due date: Friday, 4/22/2005): Read section 8.1, 8.2, 8.3.

Do exercises 8.2, 8.3, 8.4, 8.5, 8.6, and computer problem 8.1.

12th assignment: (Due date: Friday, 4/29/2005): Read section 8.4, 8.5, 15.1, 15.2.

Do exercises 8.3, 8.9, 15.2, and computer problems 8.4, 8.5, 8.6, 15.1.