- 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. - 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. - 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. - 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
^{2}= 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^{2}x + ab - ab = x, and f(h(x)) = a^{2}x - a^{2}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.

- 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
- 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.