Homework for Mathematics of Information Security
M360: Fall 2004

No computer lab on 12/3. Meet in regular classroom.

HW 14: due Friday 12/3

READ: Sections 3.10, 16.1.

BOOK PROBLEMS: 3.11.18, 3.11.19, 16.12.1, 16.12.2

OTHER PROBLEMS:
A. (Continuation of 3.12.18) What is the size of the field Z/2[x]/(x^4+x+1)?
This is the set of polynomials whose coefficients are 0 or 1 modulo the relations 2=0 and x^4+x+1=0.

B. (Continuation of 3.12.19) Consider the set F_9 of polynomials whose coefficients are 0,1,2 modulo the relations 3=0 and x^2+1=0.
Show that F_9 contains 9 elements. Show that each non-zero element of F_9 has a multiplicative inverse.

C. Consider a code where each digit (either 0 or 1) is repeated 5 times.
Suppose you encode one digit (into five). What is the largest number of errors that can still be detected?
What is the largest number of errors that can still be corrected?
If each digit has a .9 chance of being sent correctly, what is the probability that the correct message will be interpreted?
What is the information rate for this code?
What is the relative minimum distance?

D. Show that the ISBN code is a linear code by proving the following statements.
If you add two code words together, you get another valid codeword.
If you multiply a code word by a constant (and reduce mod 11) you get another valid codeword.