**Homework for Mathematics of Information Security **

M360: Fall 2004

** HW 12: due Friday 11/12**

READ: Sections 8.1,8.2,8.3. (the book uses the notation a rather than f for its secret letter)

BOOK PROBLEMS: 8.6.1, 8.6.4, 8.6.5a

OTHER PROBLEMS:

A. The hash function H from Z/25={0,1,..., 24} to Z/11={0,1,...,10} works like this.

Write m=x+y(5) where x,y are between 0 and 4. Then H(m)=(2^x)(8^y) mod 11.

For example, m=9=4+1(5) so H(m)=(2^4)(8^1) =7 mod 11.

Compute H(m) for m between 0 and 24.
Hint: the fastest way is to write H(m) as a power of 2 and use the table of powers of 2.

B. A number p is a Sophie Germaine prime if p is prime and q=2p+1 is also prime.
Find two Sophie Germaine primes p >5.

C. If p=1 mod 3, explain why p can't be a Sophie Germaine prime.