MATH 195: CRYPTOGRAPHY HOMEWORK #12

Problem 6.14. Consider a Diffie-Hellman scheme with a common prime q = 11 and a primitive root α = 2.

(a) If user A has public key Y_{A} = 9, what is A’s private key X_{A}?

(b) If user B has public key Y_{B} = 3, what is the shared secret key K?

Problem 7.17. Given 2 as a primitive root of 29, construct a table of indices, and use it to solve the following congruences:

(a) 17x^{2} ≡ 10 (mod 29);

(b) x^{2} − 4x − 16 ≡ 0 (mod 29);
(c) x^{7} ≡ 17 (mod 29).

Problem 6.25. Prove that 𝔽_{9} = 𝔽_{3}[X]/(X^{2} +1) is a field of 9 elements, determine ord(g) for all g ∈ 𝔽_{9}^{∗}, and find a primitive root for 𝔽_{9}.

Problem 6.26. Let p be a prime number for which 2^{p} − 1 is prime (q = 2^{p} − 1 is called a Mersenne prime), and let f ∈ 𝔽_{2}[X] be irreducible of degree p. Let 𝔽_{2^{p}} be the field 𝔽_{2}[X]/(f). Prove: X is a primitive root for 𝔽_{2^{p}}, i.e. ⟨X⟩ = 𝔽_{2^{p}}^{∗}.

Date: April 23, 2002.

6.14, 7.17, 6.25, 6.26.