Mathematics of Information Security
Computer Lab 5. M360. Friday 11/12/2004

Goals for today: Pseudo-random numbers and Signatures (These problems are part of the homework set due Friday 11/19, so you can try whichever you like).

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.

0. Find the period per(r) of the Fibonacci sequence mod r for several values of 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. 8.7.1. Hint for b) see pages 180-181.

D. 8.7.2.

Printing:
Do not print your whole document. It is too long. Open a new file and copy the good stuff.