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., 57850454138433 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: 2B -> 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: 2B -> 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.
  5. Let A be a subset of a subset B of a group G. Prove that CG(B) is a subgroup of CG(A): we know that centralizers are subgroups of G, so it is enough to show that CG(B) is a subset of CG(A). So let g be an element of CG(B). We must show that g is in CG(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 CG(B). Thus g is indeed in CG(A), as we wanted to show.