CS 70 Discrete Mathematics and Probability Theory
Spring 2019 Ayazifar and Rao Midterm 2 Solutions
PRINT Your Name: Oski Bear SIGN Your Name: OS K I
1. TRUE or FALSE? 2 points each
For each of the questions below, answer TRUE or FALSE. No need to justify answer.
Please fill in the appropriate bubble!
Answer: Note that the answers provide explanations for your understanding, even though no such justifica- tion was required
1. If the set of prime numbers that divide x is the same as the set of prime numbers that divide y, then x=y.
Answer: False. Consider p2 and p.
2. For primes p and q, the function f (x) = xk( p−1)(q−1)+1 (mod pq) is a bijection for all integers k.
Answer: True. This is the proof that RSA encryption/decryption returns the original message, which means it is the identity function. The identity is a bijection.
3. Every degree exactly d polynomial over GF(p) can be factored into d polynomials of degree 1, for all d and all primes p.
Answer: False. This is equivalent to stating that there are d roots. Not all polynomials have d roots as there are more polynomials than there are polynomials with d roots.
4. Let a “probability problem” be a math problem written in LATEX for which the answer is a probability. There exists a bijection between the set of probability problems and the interval [0, 1].
Answer: False.ThesetoftextwritteninLATEXiscountable,whereasthesetofrealnumbersisnot.
5. Given events A and B in a probability space, the events are independent if and only if A ∩ B is empty. Answer: False. They are disjoint but definitely not independent: Pr[A|B] = 0 where Pr[A] > 0, if A is non-empty.
6. Suppose we flip 3 fair coins, let A be the event that all the flips are the same and let B be the event that there are more heads than tails. The events A and B are independent.
Answer: True. Pr[A|B] = Pr[A] = 1/4.
7. A, B and C being pairwise independent implies that A, B and C are mutually independent.
Answer: False. Consider the events in a two coin experiment where A = HH,TT,B = {HT,TH}, and C = {HH,HT}, Pr[B|A∩C] = 0 ̸= Pr[B].
Do not turn this page until your instructor tells you to do so.
CS 70, Spring 2019, Midterm 2 Solutions 1
SID:
2. Short Answer: RSA. 3 points each.
Write your answer in the simplest form possible. You should use only the variables in the question unless otherwise specified.
1. Given an RSA scheme with public key, (N,e), and the encryptions E(x) = x′ and E(y) = y′, what is the encryption of xy? (It should be a function of x′, y′, e, N. You are not given x or y.)
Answer:x′y′ (modN).E(xy)=(xy)e=xeye (modN).
2. What is [8(7−1 (mod 5))(7) + 6(5−1 (mod 7))(5)] (mod 5)? (Answer should be in simplest terms.) Answer: 3. This is the argument for the correctness of 2-modulus CRT, which amounts to any multiple of 5 evaluates to 0 and (7−1 (mod 5))7 evaluates to 1 (mod 5).
3. Let f(x) = x7 (mod 143 = 11·13), where f : {0,1,2,…,142} → {0,1,2,…,142}. Whatisthesizeoftherangeof f?
Answer: 143. Valid encryption function, so must be bijective.
4. Let Bob have a public key of (N,e) = (77,13). What is his corresponding private key d? Answer:13−1 (mod60)=37.
5. Foranaturalnumbern≥1,ifa7 =3 (mod n)anda2 =4 (mod n),whatisa11 (mod n)? Answer: 48 (mod p). a11 = (a7)(a2)2 = 48 (mod p). Similar idea is used in repeated squaring.
6. For primes p and q, what is the probability that a random element of {0,…,pq−1} is a multiple of p or q?
Answer: p+q−1 . The number of multiples of p is q and the number of multiples of q is p, and we pq
double counted 0.
3. Polynomials++: Short Answer. 3 points each.
Write your answer in the simplest form possible. You should use only the variables in the question unless otherwise specified.
1. Consider that P(x) = 3×2 + a1x + s (mod 5) encodes a secret s as P(0); given P(1) = 3, P(2) = 4, what is the secret?
Answer:s=3 (mod5).Wehavetheequations3+a1(1)+s=3 (mod5)andtheequation3(22)+ a1 (2) + s = 4 (mod 5). The first implies that a1 = −s, plugging into the second yields s = 3 (mod 5).
2. Given polynomial P(x) of degree d with rP roots and E(x) of degree k with rE roots, what is the maximum number of roots that Q(x) = P(x)E(x) can have? (Assume P(x),E(x) are over reals.) Answer: rP + rE . The polynomials can be factored into their roots.
3. Given a polynomial P(x) and 7 ordered pairs (x1,r1),…,(x7,r7) where ri = P(xi) except for at x1 and x5. That is, P(x1) ̸= r1 and P(x5) ̸= r5. What is the error locator polynomial in the Berlekamp-Welch algorithm?
Answer: (x − x1)(x − x5).
In this problem, we will be working with polynomials over GF(p) where p is a prime, unless otherwise specified. Furthermore, when we say we pick a polynomial of degree at most k at random, we pick P(x) = akxk +ak−1xk−1 +···+a1x+a0 where ai are chosen uniformly at random from {0, …, p − 1}.
4. Assuming k < p, how many degree at most k polynomials are there over GF(p)?
Answer: pk+1. Either specify the polynomial with k + 1 points or k + 1coefficients where each is chosen from p possibilities.
2
SID:
5. Given 2 distinct values x1 and x2 (mod p), we pick a polynomial P(x) of degree at most 3 at random. What’s the probability that P(x1) = P(x2) (mod p)?
Answer: 1/p. There are p4 polynomials specified by 4 points, a point value assigned to P(x1) specifies two points, thus one can only pick two more, leaving p3 total possibilities. Dividing yields the result.
6. Now suppose you have five distinct values x1,x2,x3,x4,x5, and P(x) is again a polynomial of degree at most 3 chosen at random. What is the probability that P(x1) = P(x2) = P(x3) = P(x4) = P(x5)? (Careful.)
Answer: 1/p3. The polynomial must be a constant of which there are p possibilities out of p4 poly- nomials as we specified above.
7. How many polynomials of degree at most 5 in GF(p) have exactly 5 fixed points? (A fixed point for
P(x) is a value a where P(a) = a. Assume p ≥ 6.)
Answer: p · (p − 1). Pick the locations of the fixed points, then pick any sixth point to not be a 5
fixed point, then the interpolated polynomial cannot have any other fixed points, else it intersects with P(x) = x at six locations.
8. Let P(x) be a degree exactly 4 polynomial with a leading coefficient of 1 and fixed points at 1, 2, 3 and 4. What is P(5)? (Hint: consider P(x) − x.)
Answer: 29. P(x) = (x−1)(x−2)(x−3)(x−4)+x. The product is 0 at 1,2,3,4 and the addition of x yields the fixed points above. P(5) = 5 + (4)(3)(2)(1) = 29.
9. What is the probability that a randomly chosen polynomial modulo a prime p of degree at most d has exactly d distinct roots? (Assume p > d.)
Answer: (dp)(p−1). Form the polynomial by the location of the d roots, and the leading coefficient. pd+1
4. Countability. 5 points each part.
We say a set A ⊆ Q is downward closed if, for each x ∈ A, every rational number smaller than x is also in A. Let DQ be the set of all downward closed subsets of Q and let DLQ be the set of all downward closed subsets of Q that have a largest element.
For example, the set S of all rationals less than √2 is downward closed. It is, however, not in DLQ as S does not have a largest element.
1. Prove that DLQ is countably infinite. (Hint: find a bijection b : DLQ → Q)
Answer: Assuggestedinthehint,wefindabijectionbetweenDLQandQbylettingb(A)bethelargest element of A. This function is onto since for any q ∈ Q, the set {r ∈ Q|r ≤ q} is in DLQ and gets mapped to q by b. To prove it is one-to-one, suppose we have two sets A and B in DLQ such that f (A) = f (B). This means that both A and B have the same largest element, q. By the definition of largest, this means that neither A nor B can have any elements larger than q. Since A and B are downward closed, we know that they both contain all elements smaller than q in addition to q itself. Hence, A = B, and so b is one-to-one.
Since we have now found a bijection between DLQ and a countably infinite set, we have that DLQ is countably infinite.
2. Prove that DQ is uncountable. (Hint: find a one-to-one function f : R → DQ. You may use without proof the fact that for any x,y ∈ R with x < y, there exists a q ∈ Q such that x < q < y.)
Answer: Following the hint, we define f : R → DQ by f(x) = {r ∈ Q|r < x}. To show that this function is one-to-one, let x,y ∈ R with x ̸= y by f(x) = f(y); we can assume WLOG that x < y. By thehint,weknowthatthereissomeq∈Qwithx
Answer: n!/6. n ways to pick positions for 1, 2 and 3, and (n − 3)! ways to permute the remaining 3
objects.
For each permutation σ of 1 through n, let σ(i) denote the value at position i. For example, if the permutation is 2,4,1,3, we have σ(1) = 2 and σ(2) = 4.
4. Forafixed1≤k≤n,howmanypermutationsσ of1throughnaretherewhereforalli
losing is 0 both cases. So Emaan might as well wait until the last two.
5. Given Emaan plays optimally, find the probability Emaan wins.
Answer: 38. As noted, if the last two cards are same color, Emaan waits one turn, and then bet. 51
Otherwise, coin flip on the upcoming card. Gives us 25 + 1 · 26 51 2 51
8