Problem Set 11 Solutions PDF

Preview

Summary

Mathematics for Computer Science December 11, 2019 Massachusetts Institute of Technology 6.042/18 Zachary Abel, Ankur Moitra, and Ronitt Rubinfeld Mock ProblemSet 11 SolutionsMock Problem Set 11 SolutionsThe Cryptography and Binary Relations lectures/recitations will be covered on the final exam, so...

Description

Mathematics for Computer Science Massachusetts Institute of Technology Zachary Abel, Ankur Moitra, and Ronitt Rubinfeld

December 11, 2019 6.042/18.062J Mock Problem Set 11 Solutions

Mock Problem Set 11 Solutions The Cryptography and Binary Relations lectures/recitations will be covered on the final exam, so as an optional study resource, this is a simulation of what a problem set on those topics may have looked like. It is not due, and you are not required to study these problems in particular.

Reading Assignment Chapters 4.5.1, 4.6.4, 7.1.1, 7.4–7.8

Problem 10-1. RSA Analysis Reviewing the analysis of RSA may help you solve the following problems. You may assume results proved in class. (a) Let n be a nonnegative integer. Prove that n and n5 have the same last digit. For example: 25 = 32 795 = 3077056399 Solution: If both n and n5 have the same last digit, then n5 − n must be divisible by both 5 and 2. Thus, it is suffice to show that n5 − n ≡ 0 (mod 2) and n5 − n ≡ 0 (mod 5). For the first condition where n5 −n ≡ 0 (mod 2), there are two conditions where n ≡ 0 (mod 2) and n ≡ 1 (mod 2). The first case is trivial, and when solving for the second case, the equation becomes: n5 − n ≡ 0 (mod 2)− > 15 − 1 ≡ 0 (mod 2)− > 0 ≡ 0 (mod 2). Thus, n5 − n ≡ 0 (mod 2) is true by cases. (note: students may use FLT to show this fact). For the second condition where n5 − n ≡ 0 (mod 5), we use FLT to show that this is true. We know by FLT that for any n < 5, n4 ≡ 1 (mod 5). Thus, for any n < 5, n5 ≡ n (mod 5). Thus, n5 − n ≡ 0 (mod 5) is true. Because both statements have been proven, it is shown that n and n5 both have the same last digit. (b) Suppose that p1 , . . . , pk are distinct primes. Prove that m1+(p1 −1)(p2 −1)···(pk −1) ≡ m (mod p1 p2 · · · pk ) for all m and all k ≥ 1. Hint: Show that pj divides m1+(p1 −1)...(pk −1) − m for each j.

2

Mock Problem Set 11 Solutions Solution: If m is a multiple of a prime pj , then m1+(p1 −1)(p2 −1)···(pk −1) ≡ m (mod pj )

(*)

holds, because both sides are congruent to 0. If m is not a multiple of pj , then congruence (*) still holds because: m1+(p1 −1)(p2 −1)···(pk −1) ≡ m · (mpj −1 )(p1 −1)(p2 −1)···(pk −1)/(pj −1) (mod pj ) ≡ m · 1(p1 −1)(p2 −1)···(pk −1)/(pj −1) (mod pj ) ≡ m (mod pj ) The second step uses Fermat’s Theorem. Now the congruence (*) means that: pj | m1+(p1 −1)(p2 −1)···(pk −1) − m Thus, pj appears in the prime factorization of right side. Since this argument is valid for every prime pj where 1 ≤ j ≤ k, all of the primes p1 , . . . , pk appear in the prime factorization of: m1+(p1 −1)(p2 −1)···(pk −1) − m Therefore: p1 p2 · · · pk | m1+(p1 −1)(p2 −1)···(pk −1) − m Rewriting this as a congruence gives: m1+(p1 −1)(p2 −1)···(pk −1) ≡ m (mod p1 p2 · · · pk )

Problem 10-2.

RSA Decryption

Using the RSA encryption system, Pete the publisher generates a private key (d, n) and posts a public key, (e, n), which anyone can use to send encrypted messages to Pete. RSA has the useful property that these same keys can switch roles: if Pete wants to broadcast an unforgeable “signed” message, he can encrypt his message using his private key as though it was someone’s public key. That is, from a plain text m ∈ [0, n), Pete would broadcast a signed version, s = rem(md , n). Then anyone can decrypt and read Pete’s broadcast message by using Pete’s public key as though it were their own private key. Readers of Pete’s message can be sure the message came from Pete if they believe that the only way to generate such a message is by using the private key which Pete alone knows. (This belief is widely accepted, but not certain.)

3

Mock Problem Set 11 Solutions (a) Explain exactly what calculation must be performed on s to recover m using the public key (e, n). Explain why the calculation yields the plain text m. Solution: m = rem(se , n) The requirement for RSA decryption, namely that de ≡ 1 (mod (p − 1)(q − 1)), is symmetric in d and e, so reversing their roles allows the private key d to be used to encrypt and the public key e to decrypt. (b) Big Earl notices that the next problem on the 6.042 students’ homework seems like it could be difficult to solve without guidance (or without showing up to lecture). He decides to send the encrypted, authenticated message 1535 to the students, who can use the public key (7, 7613) to decrypt the message. Each digit of the original message corresponds to a letter of the alphabet found in the following legend: 0=u 1=e 2=o 3=i 4=b 5=s 6=h 7=c 8=x 9=k What is the original message, and to what one-word hint does it correspond? Solution: The original message is rem(15357 , 7613) = 4229 which corresponds to the word “book”.

Problem 10-3. Relations For each of the following, either prove that it is an equivalence relation and state its equivalence classes, or give an example of why it is not an equivalence relation. (a) Rn := {(x, y) ∈ Z × Z s.t. x ≡ y (mod n)} Solution: It is an equivalence relation. To prove this, we will show that Rn is symmetric, transitive, and reflexive.

4

Mock Problem Set 11 Solutions • Reflexive: x ≡ x (mod n). This is because x = x + 0 · n. • Symmetric: We want to show that Rn (x, y) ⇒ Rn (y, x). If Rn (x, y), then there is some c ∈ Z such that x = y + c · n. But then, subtracting c · n from both sides, we have that y = x + (−c) · n, so y ≡ x (mod n). So Rn (y, x), and the symmetric property holds. • Transitivity. Suppose Rn (x, y) and Rn (y, z). From the first statement, we know that there is some c ∈ Z such that x = y + c · n. From the second, we know that there is some d ∈ Z such that y = z + d · n. Substituting in this value of y, we see that x = (z + d · n) + c · n = z + (d + c) · n. The sum c + d is an integer, so Rn (x, z) holds. The equivalence classes are then the sets of numbers congruent to the numbers {0, 1, . . . , n − 1} modulo n. (b) R := {(x, y) ∈ R × R s.t. x ≥ y} Solution: This is not an equivalence relation, because the concept of symmetry is broken. If y is greater or equal to x, then x is not greater or equal to y . (c) R := {(x, y) ∈ Z × Z s.t. gcd(x, y) = 2} Solution: This is not an equivalence relation, because transitivity is broken. Consider the case when x = 6, y = 14, and z = 30. Then, gcd(x, y) = 2 and gcd(y, z) = 2, but gcd(x, z) = 6 6= 2. (d) RG := the set of (x, y) ∈ V × V such that V is the set of vertices of a graph G, and there is a path x, v1 , . . . , vk , y from x to y along the edges of G. Solution: This is an equivalence relation. We will show this by proving that it obeys reflexivity, symmetry, and transitivity. • Reflexivity: Any vertex is connected to itself. • Symmetry: If RG (x, y), then there is a path x, v1 , . . . , vk , y from x to y . The reverse of this path is y, vk , . . . , v1 , x, and is a path from y to x. So RG (y, x). • Transitivity: Suppose RG (x, y) and RG (y, z). Then, there is a path from x to y: x, v1 , . . . , vk , y . Furthermore, there is a path from y to z: y, w1 , . . . , wl , z . But then, the concatenation of those two is a path x, v1 , . . . , vk , y, w1 , . . . , wl , z from x to z. So RG (x, z). Thus we have shown that RG is an equivalence relation on a graph G, and the equivalence classes are the connected components of G.

Mock Problem Set 11 Solutions Problem 10-4.

5

Partial Orders

Answer the following questions about the powerset P({1, 2, 3, 4}) partially ordered by the strict subset relation ⊂. (a) Give an example of a maximum length chain. Solution: ∅, {1} , {1, 2} , {1, 2, 3} , {1, 2, 3, 4} .

(b) Give an example of an antichain1 of size 6. Solution: {1, 2} , {2, 3} , {3, 4} , {1, 3} , {2, 4} , {1, 4} .

(c) Describe an example of a topological sort of P({1, 2, 3, 4}). Solution: The empty set, followed by the four 1-element sets in any order, followed by the six 2-element sets in any order, followed by the four 3-element sets in any order followed by {1, 2, 3, 4}. (d) Suppose the partial order describes scheduling constraints on 16 tasks. That is, if A ⊂ B ⊆ {1, 2, 3, 4} , then A has to be completed before B starts.2 What is the minimum number of processors needed to complete all the tasks in minimum parallel time? Prove it. Solution: 6. A minimum time schedule takes max chain length steps, which is 5. There is a unique minimum task ∅ which must come first and a unique maximum task {1, 2, 3, 4} which must come last; this leaves 14 tasks which require at least ⌈14/k⌉ more parallel steps with k processors. So for min time, we need ⌈14/k⌉ ≤ 3, which implies that k ≥ 5. However, it is actually impossible to complete all of the tasks in 5 steps with 5 processors. On the first step, we must complete task ∅. On the 2nd step, we can complete tasks {1} , {2} , {3}, and {4}. We cannot complete any of the tasks of length-2 subsets, since they all depend on the subsets of length 1. On the 3rd step, 1 2

Recall that an antichain is a subset of elements where no two are comparable. As usual, we assume each task requires one time unit to complete.

6

Mock Problem Set 11 Solutions we can complete five of the tasks of length-2 subsets. Without loss of generality, assume we complete all of the length-2 subsets except for {3, 4}. Then on step 4, we can complete tasks {3, 4} , {1, 2, 3} and {1, 2, 4}, but we cannot complete the other length-3 subsets because they depend on {3, 4}. Then step 5 is {1, 3, 4} and {2, 3, 4}, and we complete step 6 with {1, 2, 3, 4}. Since it is impossible to complete the tasks in 5 steps with 5 processors, we know that we need at least 6 processors. And in fact, it is possible to complete the task in 5 steps with 6 processors:

∅ {1} , {2} , {3} , {4} {1, 2} , {1, 3} , {1, 4} , {2, 3} , {2, 4} , {3, 4} {1, 2, 3} , {2, 3, 4} , {1, 2, 4} , {1, 3, 4} {1, 2, 3, 4} .

(e) What is the length of a minimum time 3-processor schedule? Prove it. Solution: 7. For example, a length-7 3-processor schedule is: ∅ 1, 2, 3 4, 12, 23 34, 14, 24 13, 124, 234 123, 134 1234. Moreover, no shorter schedule is possible: there is a unique minimum task ∅ which must come first and a unique maximum task, {1, 2, 3, 4}, which must come last; this leaves 14 tasks which require at least ⌈14/3⌉ = 5 more parallel steps....