Homework for Mathematics of Information Security
M360: Fall 2004

HW 9: due Friday 10/22

READ: Sections 4.2, 8.1, & 3.7.

Section 6.8 #2, #7, #8, #15
Section 3.11 #15

A. DES: If K=100111010, use the DES algorithm in Section 4.2 to encrypt the message L0=010111 and R0=101000.
Specifically, find L1, R1, L2, and R2.

B. Let r=ord_n(a) be the order of a mod n. In other words, r is the smallest positive exponent so that a^r=1 mod n.
Compute ord_9(2), ord_15(2), ord_16(3), ord_10(3).

C. Let n=13. Find ord_13(a) the order of a mod 13 for each a between 1 and 12.
Which values of a have order 12 (these are called primitive roots)?

D. If a is a square mod p, where p is an odd prime, explain why it is impossible for a to be a primitive root mod p.
Hint: Write a=b^2 mod p and find an exponent e < p-1 so that a^e=1 mod p.