due Saturday, October 14, 2006, midnight
 

Re: Lecture 4 - Groups, Rings, and Fields
 

Required reading

1. W. Stallings, Cryptography and Network Security, 4th Edition


 

• Chapter 4, Finite Fields
   

2. D. Hankerson, A. Menezes, S. Vanstone, Guide to Elliptic Curve Cryptography


 

• Chapter 2.1, Introduction to finite fields (fragment of a chapter available at the book website)
   

3. A. Menezes, P. van Oorschot, and S. Vanstone, Handbook of Applied Cryptography


 

• 2.5, Abstract Algebra

• 2.6, Finite Fields

• 4.5, Irreducible polynomials over Zp

• 4.6, Generators and elements of high order.
   

Written assignment
 

Problem 6 (6 points)

For the cyclic groups

1.  (Z₂₁^*, multiplication modulo 21)

2. (Z₂₀^*, multiplication modulo 20)

3. F_2^4^* = multiplicative group of the field  F_2^4=Z₂[x]/(x⁴+x³+1)

find

a. order of the group

b. all generators of this group

c. all subgroups generated by the elements of this group.

Problem 7 (2 points)

Determine whether the polynomial

m(x) = x⁸+x⁴+x³+x+1

used in AES is primitive.

Problem 8 (4 points)

Generate tables of logarithms and antilogarithms that can be used to speed up computations in the Galois field

GF(2⁵) = Z₂[x]/f(x), where f(x) is the simplest possible primitive polynomial of the degree 5.

Use your tables to compute

b. '05' · '0F'

c. '1B' ^-1

d. '1C' · '0D'^-1