Great Theoretical Ideas In Computer Science Anupam Gupta Lecture 14 CS 15 251 October 13 2005 Fall 2005 Carnegie Mellon University Polynomials Secret Sharing And Error Correcting Codes P X X 3 X 2 X 1 Polynomials in one variable over the reals P x 3 x2 7 x 2 Q x x123 x25 19 x3 1 R y 2y 2 S z z2 z 1 T x 0 W x No Formal Power Series this time just finite polynomials Representing a polynomial A degree d polynomial is represented by its d 1 coefficients P x ad xd ad 1 xd 1 a1 x1 a0 The numbers ad ad 1 a0 are the coefficients E g P x 3x4 7x2 12x 19 Coefficients are Are we working over the reals We could work over any field set with addition multiplication division defined E g we could work with the rationals or the reals Or with Zp the integers mod prime p In this lecture we will work with Z p The Set Zp for prime p Zp 0 1 2 p 1 Zp 1 2 3 p 1 Simple Facts about Polynomials Let P x Q x be two polynomials The sum P x Q x is also a polynomial i e polynomials are closed under addition Their product P x Q x is also a polynomial closed under multiplication P x Q x is not necessarily a polynomial Evaluating a polynomial Suppose P x ad xd ad 1 xd 1 a1 x1 a0 E g P x 3x4 7x2 12x 19 P 5 3 54 7 52 12 5 19 P 1 3 1 4 7 1 2 12 1 19 P 0 19 The roots of a polynomial Suppose P x ad xd ad 1 xd 1 a1 x1 a0 Definition r is a root of P x if P r 0 E g P x 3x 7 root 7 3 P x x2 2x 1 roots 1 1 P x 3x3 10x2 10x 2 roots 1 3 1 2 The Single Most Important Fact About Low degree Polynomials A non zero degree d polynomial P x has at most d roots A Crucial Implication Two polynomials P x and Q x of degree at most d Suppose x1 x2 xd 1 are d 1 points such that P xk Q xk d 1 Then P x Q x for all values of x Proof for all k 1 2 If you give me pairs x1 y1 x2 y2 xd 1 yd 1 then there is at most one degree d polynomial P x such that P xk yk for all k Hmm at most one So perhaps there are no such degree d polynomials with P xk yk for all the d 1 values of k Lagrange Interpolation Given any d 1 pairs x1 y1 x2 y2 xd 1 yd 1 then there is exactly one degree d polynomial P x such that P xk yk for all k k th Switch polynomial k th Switch polynomial Adding them together The Lagrange Polynomial Example Input 0 1 1 2 2 9 Switch polynomials h1 x x 1 x 2 0 1 0 2 x 1 x 2 h2 x x 0 x 2 1 0 1 2 x x 2 1 h3 x x 0 x 1 2 0 2 1 x x 1 P x 1 h1 x 2 h2 x 9 h3 x 3x2 2x 1 To recap If you give me pairs x1 y1 x2 y2 xd 1 yd 1 then there is exactly one degree d polynomial P x such that P xk yk for all k And I can find this polynomial P x using Lagrange interpolation Two different representations P x ad xd ad 1 xd 1 a1 x1 a0 can be represented either by a d 1 coefficients ad ad 1 a2 a1 a0 b Its value at any d 1 points P x1 P x2 P xd P xd 1 e g P 0 P 1 P 2 P d 1 Converting between the two representations Coefficients to Evaluation Evaluation to Coefficients Some representations are better for some operations Adding two polynomials P x can be represented by a d 1 coefficients ad ad 1 a2 a1 a0 b Its value at any d 1 points P x1 P x2 P xd P xd 1 e g P 0 P 1 P 2 P d 1 Some representations are better for some operations P x can be represented by Multiplying two polynomials a d 1 coefficients ad ad 1 a2 a1 a0 b Its value at any d 1 points P x1 P x2 P xd P xd 1 e g P 0 P 1 P 2 P d 1 And some representations are better for other operations Evaluating the polynomial at some other point P x can be represented by a d 1 coefficients ad ad 1 a2 a1 a0 b Its value at any d 1 points P x1 P x2 P xd P xd 1 e g P 0 P 1 P 2 P d 1 The value representation is tolerant to erasures I want to send you a polynomial P x of degree d Suppose your mailer drops my emails once in a while Now hang on a minute Why would I ever want to send you a polynomial The value representation is tolerant to erasures I want to send you a polynomial P x of degree d Suppose your mailer drops my emails once in a while Say I wanted to send you a message hello I could write it as 8 5 12 12 15 and hence as 8 x4 5 x3 12 x2 12 x 15 The value representation is tolerant to erasures I want to send you a polynomial P x of degree d Suppose your mailer drops my emails once in a while I could evaluate P x at say n d 1 points and send k P k to you for all k 1 2 d n As long you get at least d 1 of these choose any d 1 of the ones you got and reconstruct P x But is it tolerant to corruption I want to send you a polynomial P x Suppose your mailer corrupts my emails once in a while E g suppose P x 2x2 1 and I chose n 4 I evaluated P 0 1 P 1 3 P 2 9 P 3 19 So I sent you 0 1 1 3 2 9 3 19 Corrupted email says 0 1 1 2 2 9 3 19 You choose 0 1 1 2 2 9 and get Q x Error Detecting Representation The above scheme does detect errors If we send the value of degree d polynomial P x at n d 1 different points x1 P x1 x2 P x2 xn P xn then we can detect corruptions as long as there fewer than n d of them Why If only n d 1 corruptions then d 1 correct points Also Error Correcting Representation As long as fewer than n d …
View Full Document
Unlocking...