CS 70 FALL 2006 — DISCUSSION #5D. GARMIRE, L. ORECCHIA & B. RUBINSTEIN1. Administrivia(1) Course Information• The fifth homework is due September 29that 4pm in 283 Soda Hall.(2) Discussion Information• Homework #3 is graded and will be handed out this section.2. Polynomials on the RealsBriefly, recall the following polynomial basics.Definition 1. A polynomial of degree d on the reals is a function p(x) = a0+a1x1+a2x2+ . . . + adxd, where the input variable x and the d + 1 constants a0, . . . , adareall real numbers, and additionally ad6= 0. r is a root of polynomial p(x) if p(r) = 0.Theorem 2. Over the reals:(1) A degree d polynomial has at most d roots.(2) For any (x1, y1), . . . , (xd+1, yd+1) ∈ R2there exists a unique polynomialp(x) of degree at most d such that p(xi) = yi, for each 1 ≤ i ≤ d + 1.Exercise 1. Find (and prove) an upper-bound on the number of times two degreed polynomials can intersect. What if the polynomials’ degrees differ?3. Polynomial Interpolation on the RealsProp e rty 2 (see Theorem 2) says that any set of d+1 points (x1, y1), . . . , (xd+1, yd+1) ∈R2can be interpolated by a polynomial of degree at most d. But how can weefficiently perform such an interpolation? In lecture we saw that the Lagrangeinterpolation method achieves this feat.Method 3. The Lagrange interpolation procedure:i. qi(x) =Qd+1j=1j6=i(x−xj) is a degree d polynomial satisfying qi(xj) = 0 for all j 6= iand qi(xi) is some non-zero constant;ii. ∆i(x) =qi(x)qi(xi)is a degree d polynomial equal to 1 at xiand 0 on the xjwithj 6= i;iii. yi∆i(x) is a degree d polynomial equal to yiat xiand 0 on the xjwith j 6= i;andiv. p(x) =Pd+1i=1yi∆i(x) is a polynomial of degree at most d that satisfies p(xi) =yifor each 1 ≤ i ≤ d + 1 (i.e. witnessing Property 2 as desired).Date: September 27, 2006.The authors gratefully acknowledge Chris Cru tchfield and Amir Kamil for the use of theirprevious notes, which form part of the basis for this handout.12 D. GARMIRE, L. ORECCHIA & B. RUBINSTEINExercise 2. Use the Lagrange interpolation method to determine the polynomialof degree at most 3 that fits the points (−1, 2), (0, 1), (1, 2), (2, 5). What is the(exact) degree of this polynomial?4. From Reals to Fields (e.g. Fm)Let’s start with a formal definition of a field for concreteness (don’t worry, we’renot going to be too formal today!).Definition 4. Let F be a set endowed with binary operators1+ and ×. Then F isa field if, for all a, b, c ∈ F,(i) (Closure) a + b ∈ F and a × b ∈ F;(ii) (Associativity) a + (b + c) = (a + b) + c and a × (b × c) = (a × b) × c;(iii) (Commutativity) a + b = b + a and a × b = b × a;(iv) (Distributivity) a × (b + c) = (a × b) + (a × c);(v) (Identities) there exist eleme nts 0, 1 ∈ F such that a + 0 = a and a × 1 = a;and(vi) (Inverses) there exists element −a ∈ F such that a + (−a) = 0, and if a 6= 0then there exists element a−1∈ F such that a × a−1= 1.Example 5. Valid fields include (all with + as addition and × as multiplication):(a) The reals R;(b) The rationals Q =npq| p, q ∈ Z, q 6= 0o; and(c) The integers modulo a prime m, denoted FmInvalid fields include:(d) The integers Z since there exists no multiplicative inverse for, e.g., 2; and(e) The integers modulo a composite2n denoted Znsince the prime factors of nhave no multiplicative inverse.The facts that polynomials make sense on the reals and that the two fundamentalproperties hold for polynomials on R both follow from the fact that R is a field.This proves the following.Corollary 6. For any field F, polynomials are defined just as for R. Furthermoreboth properties of Theorem 2 hold for polynomials on F; and the Lagrange interpo-lation algorithm still interpolates any given d + 1 points in F2with a polynomial ofdegree at most d on F.5. Secret SharingRecall from class the following application of Lagrange interp olation on Fm. AGSI wishes to distribute secret s ∈ Z among n CS70 students 1, . . . , n so that atleast k of these students must get together in order to reconstruct s from each oftheir pieces of information.Protocol 7. The secret sharing protocol:i. The GSI and students agree on a prime q > n, s.1Binary operators take two elements of F as input—think +(a, b) or a + b as the + operatoracting on p oi nts a, b ∈ F.2A non-prime integer.CS 70 FALL 2006 — DISCUSSION #5 3ii. The GSI picks (in secret) any k − 1 degree polynomial P (x) on Fqsuch thatP (0) = s.iii. The GSI distributes P (i) to student i, for each 1 ≤ i ≤ n.iv. Any group of k students can get together and construct the (at most) k − 1degree Lagrange polynomial L(x) that fits their respective P (i) values.v. Property 2 ensures that L = P and so that L(0) = P (0) = s.Exercise 3. Suppose (!) you’re a CS70 student, and your GSI has distributed asecret s to 10 students including yourself and your neighbor. The GSI picked apolynomial P (x) of degree 2 (and so s/he hopes that no fewer than k = 3 studentscould reconstruct s) modular q = 11. Suppose the two of you are told that P (6) ≡ 7mod 11 and that P (7) ≡ 5 mod 11. What can you say about s?Exercise 4. What if you make friends with another student who tells you thatP (8) ≡ 7 mod 11? If possible, determine
View Full Document
Unlocking...