**Homework for Mathematics of Information Security **

M360: Fall 2004

** HW 13: due Friday 11/19**

READ: Sections 2.10, 2.11.

BOOK PROBLEMS: 2.13.14, 8.7.1, 8.7.2 (the book uses the notation a rather than f for its secret letter)

OTHER PROBLEMS:

A. The following command gives you the first 40 terms of the fibonacci sequence:

f[1]:=1; f[2]:=1; for n from 3 to 40 do f[n]:=f[n-1]+f[n-2] od;

To find a pseudo-random sequence of numbers between 0 and r-1, we can look at the fibonacci sequence mod r.
For example, if r=2, type

f[1]:=1; f[2]:=1; for n from 3 to 40 do f[n]:=f[n-1]+f[n-2] mod 2 od;

We are interested in the period per(r) which tells you how long it takes for the Fibonacci sequence to repeat mod r.

1. How many r can you find so that per(r) is not a multiple of 4?

2. Find a formula for per(r) when r is a prime ending in 3 or 7.

3. Find a formula for per(r) when r is a prime ending in 1 or 9.

4. If gcd(r,s)=1, find a formula for per(rs) in terms of per(s) and per(s).

B. Find the period of each of these recursive sequences mod 2.

1. If f[1]:=1; f[2]:=0; and f[n]:=f[n-1]+f[n-2].

2. If f[1]:=1; f[2]:=0; f[3]:=0; and f[n]:=f[n-1]+f[n-3].

3. If f[1]:=1;f[2]:=0; f[3]:=1; f[4]:=0; and f[n]:=f[n-1]+f[n-4].

4. If f[1]:=0; f[2]:=1; f[3]:=0; f[4]:=0; f[5]:=0; and f[n]:=f[n-3]+f[n-5].

5. What's going on?

C. Give a description of all polynomials of degree 5 with coefficients either 0 or 1 which are irreducible mod 2.