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

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.