M417 Homework 5 Solutions Spring 2004

1. The RSA cipher, with public key n = 7822643 and encryption exponent e = 17, was used to encrypt a message. The ciphertext is: 5785045 6445108 3550040 475858 5843081. Determine the decryption exponent and the original plaintext message: We first must factor n. Using the web form on the M417 classpage, we see that n = p*q, where p = 2633 and q = 2971. We now must find the inverse d of e = 17 in U(phi(n)). But phi(n) = (p - 1)(q - 1) = 7817040, so we must find a solution d and x to de + x*phi(n) = 1. Using the web form, we have 4138433*17 - 9*7817040 = 1, so d = 4138433 (and x = -9, but we don't care about x). Now using the web form raise each number in the cipher text to the d-th power, mod n; e.g., 5785045^4138433 mod n = 805. Here's what we get: 0805 1212 1523 1518 1204. This translates to HELLOWORLD.
2. If f: A -> B is a surjective function, show that f ^-1: 2^B -> ^B is injective. To see this, let C and D be distinct subsets of B. We must show f ^-1(C) and f ^-1(D) are different. Since C and D are different, one must have an element not contained in the other. Say c is in C but c is not in D. Since f is surjective, there is an element a in A such that f(a) = c, hence f(a) is in C but not in D, so a is in f ^-1(C) but a is not in f ^-1(D). Thus f ^-1(C) and f ^-1(D) are different, so f ^-1 is injective.
3. What can you say if f in the previous problem is injective? Write down and prove a statement: If f: A -> B is an injective function, show that f ^-1: 2^B -> ^B is surjective. To see this, let D be a subset of A. We must show f ^-1(C) = D, for some subset C of B. Take C = f(D); then f ^-1(C) = f ^-1(f(D)), but by our previous homework assignment, we know that f ^-1(f(D)) = D, since f is injective.
4. Let G be the set of all maps f : R -> R of the form f(x) = ax + b, where |a| = 1, and b is an integer.
   • Show that G is a group under composition of functions: clearly G is not empty, and given any f(x) = ax + b and g(x) = a'x + b' in G, we have f(g(x)) = a(a'x + b') + b = aa'x + (ab' + b). But a, b' and b are integers, so (ab' + b) is too, and |aa'| = |a||a'| = 1² = 1. Thus f(g(x)) is in G, so composition gives a binary operation on G. Also, composition of functions is associative, and f(x) = x is an identity element for G. Finally, given f(x) = ax + b in G, its inverse is h(x) = ax - ab, since h(f(x)) = a²x + ab - ab = x, and f(h(x)) = a²x - a²b + b = x. Thus G is a group.
   • For each g in G, find C_G(g): given any g(x) in G, then f(x) is in C_G(g) exactly when f(g(x)) = g(f(x)). First say g(x) = x. Then f(g(x)) = f(x) = g(f(x)) for every f(x) in G, so C_G(g) = G. (Note that in this case g(x) is the group identity, which always commutes with every element.) Now say g(x) = x + b with b not 0. Then, for some f(x) = ax + c, we have f(g(x)) = ax + ab + c, and g(f(x)) = ax + c + b, so f(g(x)) = g(f(x)) exactly when ab = b, or a = 1. Thus C_G(g) = {f(x) = x + c : c is an integer}. Finally, say g(x) = -x + b. Then f(g(x)) = -ax + ab + c, and g(f(x)) = -ax - c + b, so f(g(x)) = g(f(x)) exactly when ab + c = -c + b, or -2c = (a - 1)b. So if a = 1, then c must be 0, and if a = -1, then c must equal b, so either f(x) = x or f(x) = g(x). Thus in this case C_G(g) = {e, g}, where e is the group identity.
   • Find Z(G): Z(G) = {f(x) = x}, since f(x) = -x + n does not commute with anything but itself and g(x) = x, and, for n not 0, f(x) = x + n does not commute with g(x) = -x.
5. Let A be a subset of a subset B of a group G. Prove that C_G(B) is a subgroup of C_G(A): we know that centralizers are subgroups of G, so it is enough to show that C_G(B) is a subset of C_G(A). So let g be an element of C_G(B). We must show that g is in C_G(A); i.e., that gx = xg for all x in A. But if x is in A, then x is in B since A is a subset of B, and we know gx = xg when x is in B, since g is in C_G(B). Thus g is indeed in C_G(A), as we wanted to show.