Mathematics 243, section 1 – Algebraic Structures Solutions for Exam 3 – December 1, 2006

I. In an RSA public key cryptosystem, the public key information is m = 323 and e = 11. Messages consisting of capital roman letters and blanks are encoded as 3-digit blocks 000, 001, ⋯, 026 (with A = 000, B = 001, ... , Z = 025, and blank = 026) and encrypted as 3-digit blocks.

A) (15) How would the letters US be encrypted?

Solution: The encryption function is f(x) = x^{11} mod 323. We have U = 020 so U is encrypted as 20^{11} mod 323. To compute this, we can use repeated squaring:

20^{2} = 400 ≡ 77 mod 323, 20^{4} ≡ 77^{2} = 5929 ≡ 115 mod 323, 20^{8} ≡ 115^{2} ≡ 305 mod 323.

Then

20^{11} = 20^{8} · 20^{2} · 20 ≡ 305 · 77 · 20 ≡ 58 mod 323.

Similarly, S = 018, and 18^{2} ≡ 1 mod 323, so S is encrypted as

18^{11} ≡ 18 mod 323

So US is encrypted as 058, 018.

B) (10) What is the (secret) decryption function g?

Solution: By the specifications for RSA systems, since 323 = 17 · 19, g is the function g(x) = x^{d} mod 323, where 11d ≡ 1 mod (17 − 1)(19 − 1) = 288. We can carry out the Euclidean algorithm to find d:

\begin{aligned}288 & = 26 · 11 + 2 \\ 11 & = 5 · 2 + 1 \end{aligned}

(so gcd(11, 288) = 1 and 11 has a multiplicative inverse mod 288). Then

1  0
0  1
26 1 −26
5 −5 131

So (−5)(288) + (131)(11) = 1, and the multiplicative inverse of 11 mod 288 is 131. Hence d = 131.

II. (20) Let

H = \{A = ( \begin{matrix}a & 0 \\ b & c \end{matrix} ) : a, b, c ∈ R and a, c ≠ 0\}

Is H a group under the operation of matrix multiplication? If so, give a proof. If not, say which of the group properties fail.

Solution: H is a group. This is true because, first, if

A = ( \begin{matrix}a & 0 \\ b & c \end{matrix} ) and A′ = ( \begin{matrix}a′ & 0 \\ b′ & c′ \end{matrix} )

then

AA′ = ( \begin{matrix}a & 0 \\ b & c \end{matrix} ) ( \begin{matrix}a′ & 0 \\ b′ & c′ \end{matrix} ) = ( \begin{matrix}aa′ & 0 \\ ba′ + cb′ & cc′ \end{matrix} )

This is also an element of H, so H is closed under products. Next, matrix multiplication is associative. The identity matrix ( \begin{matrix}1 & 0 \\ 0 & 1 \end{matrix} ) is in H (take a = c = 1 and b = 0), so H has an identity element for matrix multiplication. Finally,

A = ( \begin{matrix}a & 0 \\ b & c \end{matrix} ) ⇒ A^{−1} = ( \begin{matrix}1/a & 0 \\ −b/(ac) & 1/c \end{matrix} )

Since this is also in H every element in H has a multiplicative inverse in H. Therefore H is a group.

III. Let G be a group, let a ∈ G be a fixed element, and consider the mapping ℓ_{a} : G → G defined by ℓ_{a}(x) = ax for all x ∈ G. A) (10) Show that ℓ_{a} is one-to-one and onto.

Solution: ℓ_{a} is one-to-one since if x, y ∈ G, then

ℓ_{a}(x) = ℓ_{a}(y) ⇒ ax = ay ⇒ a^{−1}ax = a^{−1}ay ⇒ ex = ey ⇒ x = y.

ℓ_{a} is onto because if y ∈ G is any element, then ℓ_{a}(x) = y when x = a^{−1}y: ℓ_{a}(a^{−1}y) = aa^{−1}y = y.

B) (5) What is the inverse mapping of ℓ_{a}? Solution: The last part of the above shows that the inverse mapping of ℓ_{a} is ℓ_{a^{−1}} : G → G defined by ℓ_{a^{−1}}(x) = a^{−1}x.

IV. A) (15) Let G be a cyclic group with generator a. Show that every subgroup of G is also

cyclic.

Solution: Let H be a subgroup of G. If H = {e}, then H = ⟨e⟩ is cyclic. So now assume that H contains some element other than e. Since every element of G has the form a^{k} for some integer k, by the Well-Ordering Property, let k be the smallest positive integer such that a^{k} ∈ H. We will show H = ⟨a^{k}⟩. The inclusion H ⊇ ⟨a^{k}⟩ is automatic since H is a subgroup of G and a^{k} ∈ H. For the other inclusion, let a^{n} be any element in H. Apply the division algorithm in Z to write n = qk + r for some quotient q ∈ Z and remainder r ∈ Z with 0 ≤ r < k. Then

a^{n} = a^{qk+r} = (a^{k})^{q}a^{r},

which implies

a^{r} = a^{n}(a^{k})^{−q}

Since a^{n}, a^{k} ∈ H, the right-hand side is in H. Therefore a^{r} is also in H. But this is only possible if r = 0, since r < k and k was the smallest positive integer such that a^{k} ∈ H. Hence a^{n} = (a^{k})^{q} ∈ ⟨a^{k}⟩. Since every element in H is in ⟨a^{k}⟩, we have H ⊂ ⟨a^{k}⟩ also.

B) (10) G = Z_{30} is a group under the operation of addition mod 30. Find all of the generators of the cyclic subgroup H = ⟨[18]⟩.

Solution: Recall our theorem that in a cyclic group of order n with generator a, the subgroup ⟨a^{k}⟩ is the same as ⟨a^{d}⟩ where d = gcd(k, n). Here we can take a = [1] and the operation is addition, so this says ⟨[x]⟩ = ⟨[18]⟩ when gcd(x, 30) = gcd(18, 30) = 6. This gives x = 6, 12, 18, 24.

V. Let G, H be two groups.

A) (5) What is the definition of a group homomorphism from G to H?

Solution: A mapping φ : G → H is a group homomorphism if

φ(x ∗_{G} y) = φ(x) ∗_{H} φ(y)

for all x, y ∈ G.

B) (10) Let G = Z_{24} with operation addition mod 24. What is the kernel of the group homomorphism ϕ : G → G defined by ϕ([x]) = [9x]?

Solution: When φ is a general group homomorphism φ : G → H,

ker(φ) = {x ∈ G : φ(x) = e_{H}}.

Here H = G, and the additive identity element is [0] ∈ Z_{24}. So [9x] = [0] exactly when 9x ≡ 0 mod 24. Since 9 is divisible by 3, this means x must be divisible by 8: x = 0, 8, 16.