Coding Theory

Fourth Assignment: due Fri. Mar 23

1. a. Find the inverse of 37 modulo 41 using the Euclidean algorithm.
   b. Find the inverse of 41 mod 37.
   
2. a. Find the order of 2 and 5 in Z/31 .
   b. Find a primitive element in Z/31 .
   
3. a. Make a list of all the polynomials over F_2 of degree at most 4 with non-zero constant term. Show the factorization of all the reducible polynomials in the list. Identify the irreducible polynomials in the list.
   
4. a. Find the inverse of x^3 + x + 1 modulo x^5 + x + 1 , using the Euclidean algorithm.
   b. Find the inverse of x^5 + x + 1 modulo x^3 + x + 1 .
   c. Interpret your results with respect to the fields F_8 and F_32 .
   
5. Construct F_9 .
   a. Make a list of all the monic polynomials over F_3 of degree 2 with non-zero constant term. Show the factorization of all the reducible polynomials in the list. Identify the irreducible polynomials in the list.
   b. Choose one of the irreducible polynomials and create F_9 by adjoining a root of this polynomial, alpha, to F_3 . Show the correspondence between powers of alpha and linear polynomials in alpha.
   c. Find the minimal polynomial of each element of F_9 .
   d. What are the primitive elements of F_9 ?