Homework for Mathematics of Information Security
M360: Fall 2004

HW 11: due Friday 11/5

OFFICE HOURS: this week office hours will be Wed 2-3 and Fri 10-11.

READ: Handout (available on my office door or in class on Wed).

BOOK PROBLEMS: Handout 21.1 a,c, 21.3.

A. Use Maple to show that 3 is a primitive root mod 31 and compute the table of powers of 3.
Use this table to find the order of every a between 1 and 30. For which exponents e is 3^e a primitive root mod 31?

B. Suppose p=21169. How many primitive roots are there mod p? If g is a primitive root mod p, which of the numbers g^1, g^2, ...g^20 is also a primitive root?

C. Use Maple to find the set SQUARE31={x^2 mod 31 as x ranges from 1 to 30}.
For each a in the set SQUARE31, use the table from Problem A to write a=3^e for some exponent e.
For example 5=6^2 mod 31 so 5 is in the set SQUARE31 and 5=3^20 mod 31 so e is 20 in this case.
Finish this conjecture: Suppose g is a primitive root mod p and a=g^e for some exponent e. Then a=x^2 mod p has a solution if and only if e is ______.

D. Prove the Conjecture from Problem B.

E. Alice works for a company that has just made a job offer to Bob. It turns out that Alice and Bob are friends and she would like to help him negotiate the offer.
Since all her e-mail is watched by the company's anti-privacy server, they decide to use the El Gamal cryptosystem.

1. Bob chooses the prime p=65537. Show that a=3 is a primitive root mod p.
Hint: it will take too long to compute 3^i for all i between 1 and 65536.
Make a short list of the possible values for the order of 3 mod p and check all of these with successive squaring.

2. Bob chooses a secret value f=617. He computes b=a^f mod p. What is b?

3. Bob publishes (p,a,b). Explain why no one else can (easily) find f.

4. Alice decides to test the system with the message "hibob". She chooses a secret value k=13.
She breaks her message into 2 parts ("hi" and "bob") and converts the parts to numbers m and n.
Alice sends the numbers (c1:=a^k mod p, c2:=b^k*m mod p) (d1:=a^k mod p, d2:=b^k*n mod p) to Bob. What are these numbers?

5. Bob tests the decryption with the formula m=c2*c1^(-f) mod p and n=d2*d1^(-f) mod p. Check to make sure your decryption process works.

6. Alice's next message is (21435, 24019), (21435, 46689), (21435, 40131). What is she telling Bob?

* (Bonus) We say that a is a primitive root mod n if phi(n) is the order of a mod n.
List all the values of n between 1 and 50 for which there is at least one primitive root mod n.
Make a conjecture about this list.

** (Bonus) Find the order of 2 mod n for every odd n between 3 and 99.
Make a conjecture about how these numbers are related.
Can you use this data to find the order of 2 mod 155?