Homework for Mathematics of Information Security
M360: Fall 2004

HW 13: due Friday 11/19

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.