DOC PREVIEW
Berkeley COMPSCI 70 - n7

This preview shows page 1-2-3 out of 8 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 8 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 8 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 8 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 8 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

EECS 70 Discrete Mathematics and Probability TheorySpring 2014 Anant Sahai Note 7PolynomialsPolynomials constitute a rich class of functions which are both easy to describe and widely applicablein topics ranging from Fourier analysis, cryptography, and communication, to control and computationalgeometry. They show up in all sorts of EECS courses including 70’s sister course 20, and then in the upper-division courses like 120, 123, etc. In this note, we will discuss some properties of polynomials which makethem so useful. We will then describe how to take advantage of these properties to develop a secret sharingscheme.Recall from your high school math that a polynomial in a single variable is of the form p(x) = adxd+ad−1xd−1+ ··· + a0. Here the variable x and the coefficients aiare usually real numbers. For example,p(x) = 5x3+ 2x + 1, is a polynomial of degree d = 3. Its coefficients are a3= 5, a2= 0, a1= 2, and a0= 1.Polynomials have some remarkably simple, elegant and powerful properties, which we will explore in thisnote.First, a definition: we say that a is a root of the polynomial p(x) if p(a) = 0. For example, the degree2 polynomial p(x) = x2− 4 has two roots, namely 2 and −2, since p(2) = p(−2) = 0. If we plot thepolynomial p(x) in the x-y plane, then the roots of the polynomial are just the places where the curve crossesthe x axis:We now state two fundamental properties of polynomials that we will prove in due course.Property 1: A non-zero polynomial of degree d has at most d roots.Property 2: Given d + 1 pairs (x1,y1),...,(xd+1,yd+1), with all the xidistinct, there is a unique polynomialp(x) of degree (at most) d such that p(xi) = yifor 1 ≤ i ≤ d + 1.Let us consider what these two properties say in the case that d = 1. A graph of a linear (degree 1) polynomialy = a1x +a0is a line. Property 1 says that if a line is not the x-axis (i.e. if the polynomial is not y = 0), thenit can intersect the x-axis in at most one point.EECS 70, Spring 2014, Note 7 1Property 2 says that two points uniquely determine a line.Polynomial InterpolationProperty 2 says that two points uniquely determine a degree 1 polynomial (a line), three points uniquelydetermine a degree 2 polynomial, four points uniquely determine a degree 3 polynomial, and so on. Givend +1 pairs (x1,y1),...,(xd+1,yd+1), how do we determine the polynomial p(x) = adxd+··· + a1x + a0suchthat p(xi) = yifor i = 1 to d + 1? We will give a very simple algorithm1for reconstructing the coefficientsa0,...,ad, and therefore the polynomial p(x).The method is called Lagrange interpolation: Let us start by solving an easier problem. Suppose thatwe are told that y1= 1 and yj= 0 for 2 ≤ j ≤ d + 1. Now can we reconstruct p(x)? Yes, this is easy!Consider q(x) = (x − x2)(x − x3)···(x − xd+1). This is a polynomial of degree d (the xi’s are constants, andx appears d times). Also, we clearly have q(xj) = 0 for 2 ≤ j ≤ d + 1. But what is q(x1)? Well, q(x1) =(x1− x2)(x1− x3)···(x1− xd+1), which is some constant not equal to 0. Thus if we let p(x) = q(x)/q(x1)(dividing is ok since q(x1) 6= 0), we have the polynomial we are looking for. For example, suppose you weregiven the pairs (1,1), (2,0), and (3,0). Then we can construct the degree d = 2 polynomial p(x) by lettingq(x) = (x −2)(x−3) = x2−5x + 6, and q(x1) = q(1) = 2. Thus, we can now construct p(x) = q(x)/q(x1) =(x2− 5x + 6)/2.Of course the problem is no harder if we single out some arbitrary index i instead of 1: i.e. yi= 1 and yj= 0for j 6= i. Let us introduce some notation: let us denote by ∆i(x) the degree d polynomial that goes throughthese d + 1 points. Then ∆i(x) =Π j6=i(x−xj)Π j6=i(xi−xj).Let us now return to the original problem. Given d + 1 pairs (x1,y1),...,(xd+1,yd+1), we first construct thed + 1 polynomials ∆1(x),...,∆d+1(x). Now we can write p(x) =∑d+1i=1yi∆i(x). Why does this work? Firstnotice that p(x) is a polynomial of degree d as required, since it is the sum of polynomials of degree d. Andwhen it is evaluated at xi, d of the d + 1 terms in the sum evaluate to 0 and the i-th term evaluates to yitimes1, as required.As an example, suppose we want to find the degree-2 polynomial p(x) that passes through the three points1Another linear-algebra based algorithm that is more computer friendly is given in the next note.EECS 70, Spring 2014, Note 7 2(1,1), (2,2) and (3, 4). The three polynomials ∆iare as follows: If d = 2, and xi= i, for instance, then∆1(x) =(x − 2)(x − 3)(1 − 2)(1 − 3)=(x − 2)(x − 3)2=12x2−52x + 3;∆2(x) =(x − 1)(x − 3)(2 − 1)(2 − 3)=(x − 1)(x − 3)−1= −x2+ 4x − 3;∆3(x) =(x − 1)(x − 2)(3 − 1)(3 − 2)=(x − 1)(x − 2)2=12x2−32x + 1.The polynomial p(x) is therefore given byp(x) = 1 · ∆1(x) + 2 · ∆2(x) + 4 · ∆3(x) =12x2−12x + 1.You should verify that this polynomial does indeed pass through the above three points.Proof of Property 2We would like to prove property 2:Property 2: Given d + 1 pairs (x1,y1),...,(xd+1,yd+1), with all the xidistinct, there is a unique polynomialp(x) of degree (at most) d such that p(xi) = yifor 1 ≤ i ≤ d + 1.We have shown how to find a polynomial p(x) such that p(xi) = yifor d + 1 pairs (x1,y1),...,(xd+1,yd+1).This proves part of property 2 (the existence of the polynomial). How do we prove the second part, that thepolynomial is unique? Suppose for contradiction that there is another polynomial q(x) such that p(xi) = yifor all d + 1 pairs above. Now consider the polynomial r(x) = p(x) − q(x). Since we are assuming that q(x)and p(x) are different polynomials, r(x) must be a non-zero polynomial of degree at most d. Therefore,property 1 implies it can have at most d roots. But on the other hand r(xi) = p(xi) − q(xi) = 0 on d + 1distinct points. Contradiction. Therefore, p(x) is the unique polynomial that satisfies the d + 1 conditions.Polynomial DivisionLet’s take a short digression to discuss polynomial division, which will be useful in the proof of property 1.If we have a polynomial p(x) of degree d, we can divide by a polynomial q(x) of degree ≤ d by usingelementary-school long division. The result will be:p(x) = q(x)q0(x) + r(x)where q0(x) is the quotient and r(x) is the remainder. The degree of r(x) must be smaller than the degree ofp(x).Example. We wish to divide p(x) = x3+ x2− 1 by q(x) = x − 1:X2+ 2X + 2X −1X3+ X2− 1− X3+ X22X2− 2X2+ 2X2X −1− 2X + 21EECS 70, Spring 2014,


View Full Document

Berkeley COMPSCI 70 - n7

Documents in this Course
Notes 1

Notes 1

12 pages

Note 2

Note 2

6 pages

Notes

Notes

6 pages

Notes

Notes

7 pages

Note 10

Note 10

8 pages

n20

n20

10 pages

n19

n19

10 pages

n18

n18

10 pages

n17

n17

6 pages

n16

n16

9 pages

n15

n15

10 pages

n14

n14

9 pages

n13

n13

6 pages

n12

n12

7 pages

n11

n11

6 pages

n10

n10

8 pages

n9

n9

5 pages

n8

n8

7 pages

n6

n6

5 pages

n5

n5

8 pages

n4

n4

7 pages

n3

n3

10 pages

n2

n2

7 pages

n1

n1

5 pages

Load more
Download n7
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view n7 and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view n7 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?