Homework for Mathematics of Information Security
M360: Fall 2004

HW 5: due Friday 9/24

READ: Sections 2.8, 2.9, 3.5, 3.6.
BOOK PROBLEMS: Section 2.14 #8,#9, Section 3.11 #8.
OTHER PROBLEMS:
A. Write 2004 (base 10) in binary form (base 2).

B. The numbers 1, 11, 111, 1111, 11111 are written in base 2. What are they in base 10? Can you find a formula for them?

C. Multiple encryption: What is the period if you encrypt a message first with a Vigenere cipher of period 4 and then encrypt the ciphertext with a Vigenere cipher of period 10?

D. Find all a between 0 and 19 so that 8a =0 mod 20.
Explain why this is the same as finding those with 4a=0 mod 20.

E. Use Fermat's Little Theorem (not the computer!) to find x.
1) x= 9^(794) mod 73.
2) x^(86)=6 mod 29.
3) x^(39)=3 mod 13.

Bonus:
The smallest positive number e so that a^e = 1 mod p is called the order of a mod p.
1. What is the largest possible order (depending on p)
2. What is the smallest positive number E so that every order divides E?
3. If you know the order of a mod p and the order of b mod p, what is a formula for the order of ab mod p?